{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Make Array Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组中所有元素相等的最小操作数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个长度为 <code>n</code> 的数组 <code>arr</code> ，其中 <code>arr[i] = (2 * i) + 1</code> （ <code>0 &lt;= i &lt; n</code> ）。</p>\n",
    "\n",
    "<p>一次操作中，你可以选出两个下标，记作 <code>x</code> 和 <code>y</code> （ <code>0 &lt;= x, y &lt; n</code> ）并使 <code>arr[x]</code> 减去 <code>1</code> 、<code>arr[y]</code> 加上 <code>1</code> （即 <code>arr[x] -=1 </code>且 <code>arr[y] += 1</code> ）。最终的目标是使数组中的所有元素都 <strong>相等</strong> 。题目测试用例将会 <strong>保证</strong> ：在执行若干步操作后，数组中的所有元素最终可以全部相等。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code>，即数组的长度。请你返回使数组 <code>arr</code> 中所有元素相等所需的 <strong>最小操作数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>arr = [1, 3, 5]\n",
    "第一次操作选出 x = 2 和 y = 0，使数组变为 [2, 3, 4]\n",
    "第二次操作继续选出 x = 2 和 y = 0，数组将会变成 [3, 3, 3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-make-array-equal](https://leetcode.cn/problems/minimum-operations-to-make-array-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-make-array-equal](https://leetcode.cn/problems/minimum-operations-to-make-array-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        cache = {}\n",
    "        for i, v in enumerate(target):\n",
    "            cache[v] = i \n",
    "        \n",
    "        heaps = []\n",
    "        for i, v in enumerate(arr):\n",
    "            if v in cache:\n",
    "                v = cache[v]\n",
    "                l, r = 0, len(heaps)\n",
    "                while l < r:\n",
    "                    mid = (l+r)//2\n",
    "                    if heaps[mid] >= v:\n",
    "                        r = mid \n",
    "                    else:\n",
    "                        l = mid+1\n",
    "                    \n",
    "                if l < len(heaps) and heaps[l] >= v:\n",
    "                    heaps[l] = v \n",
    "                else:\n",
    "                    heaps.append(v)\n",
    "        return len(target)-len(heaps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        pos = {}\n",
    "        for i, t in enumerate(target):\n",
    "            pos[t] = i\n",
    "        d = []\n",
    "        for val in arr:\n",
    "            if val in pos:\n",
    "                idx = pos[val]\n",
    "                if not d:\n",
    "                    d.append(idx)\n",
    "                else:\n",
    "                    l, r = -1, len(d)\n",
    "                    while l + 1 < r:\n",
    "                        mi = (l + r) // 2\n",
    "                        if d[mi] < idx:\n",
    "                            l = mi\n",
    "                        else:\n",
    "                            r = mi\n",
    "                    if r == len(d):\n",
    "                        d.append(idx)\n",
    "                    else:\n",
    "                        d[r] = idx\n",
    "        return n - len(d)\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     if target[i] == arr[j]:\n",
    "        #         return dfs(i - 1, j - 1) + 1\n",
    "        #     return max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "\n",
    "        # return len(target) - dfs(len(target) - 1, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "\n",
    "        idx_dict = {num: i for i, num in enumerate(target)}\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if num in idx_dict:\n",
    "                idx = idx_dict[num]\n",
    "                i = bisect.bisect_left(stack, idx)\n",
    "\n",
    "                if i == len(stack):\n",
    "                    stack.append(0)\n",
    "                stack[i] = idx\n",
    "        return len(target) - len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        m, n = len(target), len(arr)\n",
    "        pos = dict()\n",
    "        for i in range(m):\n",
    "            pos[target[i]] = i\n",
    "        #print(pos)\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            if not s and arr[i] in pos:\n",
    "                s.append(pos[arr[i]])\n",
    "            if arr[i] in pos:\n",
    "                #print(arr[i], s[-1])\n",
    "                if pos[arr[i]] > pos[target[s[-1]]]:\n",
    "                    s.append(pos[arr[i]])\n",
    "                else:\n",
    "                    t = bisect_left(s, pos[arr[i]])\n",
    "                    s[t] = pos[arr[i]]\n",
    "        return m - len(s)\n",
    "                   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = []\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(f) - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            if l >= len(f):\n",
    "                f.append(i)\n",
    "            else:\n",
    "                f[l] = i\n",
    "        return n - len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 把target等价转换为 01234... 后求最长递增子序列\n",
    "        table = {}\n",
    "        for i in range(len(target)):\n",
    "            table[target[i]] = i\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in table:\n",
    "                arr[i] = table[arr[i]]\n",
    "            else:\n",
    "                arr[i] = -1\n",
    "        nums = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == -1:\n",
    "                continue\n",
    "            index = bisect.bisect_left(nums,arr[i])\n",
    "            if index == len(nums):\n",
    "                nums.append(arr[i])\n",
    "            else:\n",
    "                nums[index] = arr[i]\n",
    "        return len(target) - len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i,x in enumerate(target):\n",
    "            d[x]=i\n",
    "        \n",
    "        st = []\n",
    "        for x in arr:\n",
    "            if x not in d:\n",
    "                continue\n",
    "            ind = d[x]\n",
    "            if len(st)==0 or ind>st[-1]:\n",
    "                st.append(ind)\n",
    "            else:\n",
    "                pos = bisect.bisect_left(st, ind)\n",
    "                st[pos] = ind\n",
    "        \n",
    "        return len(target)-len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # def LCS(text1, text2):\n",
    "        #     R, C = len(text1) + 1, len(text2) + 1\n",
    "        #     dp = [[0] * C for i in range(R)]\n",
    "        #     for i in range(1, R):\n",
    "        #         for j in range(1, C):\n",
    "        #             if text1[i - 1] == text2[j - 1]:\n",
    "        #                 dp[i][j] = 1 + dp[i - 1][j - 1]\n",
    "        #             else:\n",
    "        #                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n",
    "        #     return dp[-1][-1]\n",
    "        # return len(target) - LCS(target, arr)\n",
    "\n",
    "        d = {n: i for i, n in enumerate(target)}\n",
    "        def LIS(arr): # strictly increasing\n",
    "            LIS = []\n",
    "            for n in arr:\n",
    "                if n in d:\n",
    "                    i = bisect_left(LIS, d[n])\n",
    "                    if i == len(LIS):\n",
    "                        LIS.append(d[n])\n",
    "                    else:\n",
    "                        LIS[i] = d[n]\n",
    "            return len(LIS)   \n",
    "        return len(target) - LIS(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(f) - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = []\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if not f or f[-1] < i:\n",
    "                f.append(i)\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(f) - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = {num: i for i, num in enumerate(target)}\n",
    "        dp = []\n",
    "        for x in arr:\n",
    "            if x in d:\n",
    "                i = bisect.bisect_left(dp, d[x])\n",
    "                if i == len(dp):\n",
    "                    dp.append(d[x])\n",
    "                else:\n",
    "                    dp[i] = d[x]\n",
    "\n",
    "        return len(target) - len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        pos = {}\n",
    "        for i, t in enumerate(target):\n",
    "            pos[t] = i\n",
    "        d = []\n",
    "        for val in arr:\n",
    "            if val in pos:\n",
    "                idx = pos[val]\n",
    "                r = bisect.bisect_left(d, idx)\n",
    "                # l, r = -1, len(d)\n",
    "                # while l + 1 < r:\n",
    "                #     mi = (l + r) // 2\n",
    "                #     if d[mi] < idx:\n",
    "                #         l = mi\n",
    "                #     else:\n",
    "                #         r = mi\n",
    "                if r == len(d):\n",
    "                    d.append(idx)\n",
    "                else:\n",
    "                    d[r] = idx\n",
    "        return n - len(d)\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     if target[i] == arr[j]:\n",
    "        #         return dfs(i - 1, j - 1) + 1\n",
    "        #     return max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "\n",
    "        # return len(target) - dfs(len(target) - 1, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(f) - 1\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if f[m] >= i:\n",
    "                        r = m - 1\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                f[l] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # target = [5,1,3], arr = [5,9,4,2,3,4] [0, 2]\n",
    "        # d = {5: 0, 1: 1, 3: 2}\n",
    "        d = {n: i for i, n in enumerate(target)}\n",
    "        def LIS(arr): # strictly increasing\n",
    "            LIS = []\n",
    "            for n in arr:\n",
    "                if n in d:\n",
    "                    i = bisect_left(LIS, d[n])\n",
    "                    if i == len(LIS):\n",
    "                        LIS.append(d[n])\n",
    "                    else:\n",
    "                        LIS[i] = d[n]\n",
    "            return len(LIS)   \n",
    "        return len(target) - LIS(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        hash = {val: idx for idx, val in enumerate(target)}\n",
    "        # 问题转化为求最大递增子序列\n",
    "        # dp[i]表示长度为i的递增序列的最后一位\n",
    "        dp = [-float('inf')]\n",
    "        for c in arr:\n",
    "            if c not in hash:\n",
    "                continue\n",
    "            p = hash[c]\n",
    "            # print(p, end=': ')\n",
    "            if p > dp[-1]:\n",
    "                dp.append(p)\n",
    "                continue\n",
    "            if p <= dp[1]:\n",
    "                dp[1] = p\n",
    "                continue\n",
    "            # 二分查找，找到比p大的最左数字\n",
    "            left, right = 1, len(dp) - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if dp[mid] < p:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            dp[left] = p\n",
    "            # print(dp)\n",
    "        # print()\n",
    "        # print(dp)\n",
    "        return len(target) - (len(dp) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        pos = {num: i for i, num in enumerate(target)}\n",
    "        seq = []\n",
    "        for num in arr:\n",
    "            if num in pos:\n",
    "                i = pos[num]\n",
    "                idx = bisect.bisect_left(seq, i)\n",
    "                if idx == len(seq):\n",
    "                    seq.append(i)\n",
    "                else:\n",
    "                    seq[idx] = i\n",
    "        return len(target) - len(seq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "            else:\n",
    "                f[bisect_left(f, i)] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "            else:\n",
    "                f[bisect_left(f, i)] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\r\n",
    "class Solution:\r\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\r\n",
    "        # target is mapped to [0, 1, ...], finding lcs of target and arr\r\n",
    "        # is equivalent to finding lis of mapped arr\r\n",
    "        indices = {tgt: i for i, tgt in enumerate(target)}\r\n",
    "        lis: list[int] = list()\r\n",
    "        for num in arr:\r\n",
    "            if num not in indices: continue\r\n",
    "            x = bisect_left(lis, indices[num])\r\n",
    "            if x == len(lis):\r\n",
    "                lis.append(indices[num])\r\n",
    "            else:\r\n",
    "                lis[x] = indices[num]\r\n",
    "        \r\n",
    "        return len(target) - len(lis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\r\n",
    "class Solution:\r\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\r\n",
    "        # target is mapped to [0, 1, ...], finding lcs of target and arr\r\n",
    "        # is equivalent to finding lis of mapped arr\r\n",
    "        indices = {tgt: i for i, tgt in enumerate(target)}\r\n",
    "        lis: list[int] = list()\r\n",
    "        for num in arr:\r\n",
    "            if num not in indices: continue\r\n",
    "            x = bisect_left(lis, indices[num])\r\n",
    "            if x == len(lis):\r\n",
    "                lis.append(indices[num])\r\n",
    "            else:\r\n",
    "                lis[x] = indices[num]\r\n",
    "        \r\n",
    "        return len(target) - len(lis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        f[0] = -1\n",
    "        idx = 1\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 1\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        m = len(target)\n",
    "        mapper = {}\n",
    "        for i in range(m):\n",
    "            mapper[target[i]] = i\n",
    "        \n",
    "        brr = []\n",
    "        for a in arr:\n",
    "            if a in mapper.keys():\n",
    "                brr.append(mapper[a])\n",
    "        \n",
    "        n = len(brr)\n",
    "        if n == 0:\n",
    "            return m\n",
    "\n",
    "        stack = [brr[0]]\n",
    "        for i in range(1, n):\n",
    "            if brr[i] > stack[-1]:\n",
    "                stack.append(brr[i])\n",
    "            else:\n",
    "                l, r = 0, len(stack) - 1\n",
    "                while l < r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if stack[mid] < brr[i]:\n",
    "                        l = mid + 1\n",
    "                    else:\n",
    "                        r = mid\n",
    "                stack[l] = brr[i]\n",
    "        return m - len(stack)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        idx = 0\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            if l >= idx:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "            else:\n",
    "                f[l] = i\n",
    "        return n - idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict(zip(target, range(len(target))))\n",
    "        arr = list(map(lambda x: d[x], filter(lambda x: x in d, arr)))\n",
    "\n",
    "        dp = [-inf]\n",
    "        for a in arr:\n",
    "            if a > dp[-1]: dp.append(a)\n",
    "            else: dp[bisect_left(dp, a)] = a\n",
    "        return len(target) - (len(dp) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        hst = {num: i for i, num in enumerate(target)}\n",
    "        nums = []\n",
    "        for a in arr:\n",
    "            if a in hst:\n",
    "                nums.append(hst[a])\n",
    "        \n",
    "        d = []\n",
    "        for n in nums:\n",
    "            if not d or n > d[-1]:\n",
    "                d.append(n)\n",
    "            else:\n",
    "                loc =  bisect.bisect_left(d, n)\n",
    "                d[loc] = n\n",
    "        return len(target) - len(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = {num:i + 1 for i, num in enumerate(target)}\n",
    "        nums = [d[i] for i in arr if i in d]\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return len(d)\n",
    "        dp = []\n",
    "        for i in range(n):\n",
    "            pos = bisect.bisect_left(dp, nums[i])\n",
    "            if pos >= len(dp):\n",
    "                dp.append(nums[i])\n",
    "            else:\n",
    "                dp[pos] = nums[i]\n",
    "        return len(d) - len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 找target 和 arr 的最长公共子序列\n",
    "\n",
    "        # 根据target中互不相同，我们知道每个数字对应的坐标唯一\n",
    "\n",
    "        # 于是最长公共子序列等价于arr用target的坐标转换后构成对应的下标数组的“最长递增子序列”\n",
    "\n",
    "\n",
    "        # 数字对应坐标\n",
    "        idx_dict = {num: i for i, num in enumerate(target)}\n",
    "        # 300.最长上升子序列\n",
    "        dp = [0] * len(arr)\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            # 只有在target的数字才可能属于公共子序列\n",
    "            if num in idx_dict:\n",
    "                # 转换坐标\n",
    "                idx = idx_dict[num]\n",
    "                # 该坐标在当前栈中的位置\n",
    "                left, right = 0, res\n",
    "                while left + 1 < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if dp[mid] < idx:\n",
    "                        left = mid \n",
    "                    else:\n",
    "                        right = mid\n",
    "                if dp[left] >= idx:\n",
    "                    dp[left] = idx\n",
    "                    if left == res: res += 1\n",
    "                else:\n",
    "                    dp[right] = idx\n",
    "                    if right == res: res += 1\n",
    "                # 如果在最后要加入元素，否则要修改该位置的元素\n",
    "                # 跟一般的讲，i代表了目前这个idx在stack中的大小位置，\n",
    "                # 在前面出现还比idx大的stack中的元素是无法和idx构成最长上升子序列的。\n",
    "                # i左边的数比idx小，可以和idx构成上升子序列，(idx构成的长度就是i+1)\n",
    "                # idx比i的值小，将i替换后可以方便后面构成更优的子序列(越小后面能加入的数越多)\n",
    "\n",
    "\n",
    "        # 最终stack的长度就构成了最长上升子序列的长度，用减法即可得到本题答案\n",
    "        return len(target) - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        dt = dict()\n",
    "        for i, t in enumerate(target):\n",
    "            dt[t] = i\n",
    "\n",
    "        newarr = []\n",
    "\n",
    "        for a in arr:\n",
    "            if a in dt:\n",
    "                newarr.append(dt[a])\n",
    "        \n",
    "        n = len(newarr)\n",
    "\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            if not tmp:\n",
    "                tmp.append(newarr[i])\n",
    "            else:\n",
    "                if newarr[i] > tmp[-1]:\n",
    "                    tmp.append(newarr[i])\n",
    "                else:\n",
    "                    pos = bisect.bisect_left(tmp, newarr[i] )\n",
    "                    tmp[pos] = newarr[i]\n",
    "        return len(target) - len(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        dictA = dict()\n",
    "        for i,t in enumerate(target):\n",
    "            dictA[t] = i   \n",
    "        arr_map = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in dictA:\n",
    "                arr_map.append(dictA[arr[i]])\n",
    "        \n",
    "        longest = self.lengthOfLIS(arr_map)\n",
    "        return len(target) - longest\n",
    "\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        res = [nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>res[-1]:\n",
    "                res.append(nums[i])\n",
    "            else:\n",
    "                idx = bisect_left(res, nums[i])\n",
    "                res[idx] = nums[i]\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 求最长公共子序列，用n-最长公共子序列的长度就是最少插入次数\n",
    "        # 因为target数组各不相同，所以每个元素与index一一对应，\n",
    "        pos={x:i for i,x in enumerate(target)}\n",
    "        index=[]\n",
    "        for x in arr:\n",
    "            if x in pos:index.append(pos[x])\n",
    "        dp=[]\n",
    "        for x in index:\n",
    "            if not dp or x>dp[-1]:\n",
    "                dp.append(x)\n",
    "            else:\n",
    "                index=bisect.bisect_left(dp,x)\n",
    "                dp[index]=x \n",
    "        return len(target)-len(dp)\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        my_dict = {}\n",
    "        for i, x in enumerate(target):\n",
    "            my_dict[x] = i\n",
    "        \n",
    "        # Only keep the elements in arr that also exist in target\n",
    "        new_arr = [my_dict[val] for val in arr if val in my_dict]\n",
    "\n",
    "        # Find the length of LIS in new_arr\n",
    "        lis = []\n",
    "        for x in new_arr:\n",
    "            idx = self.binary_search(lis, x)\n",
    "            if idx == len(lis):\n",
    "                lis.append(x)\n",
    "            else:\n",
    "                lis[idx] = x\n",
    "\n",
    "        return len(target) - len(lis)\n",
    "    \n",
    "    def binary_search(self, lis, x):\n",
    "        l, r = 0, len(lis) - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if lis[mid] < x:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        my_dict = {}\n",
    "        for i, x in enumerate(target):\n",
    "            my_dict[x] = i\n",
    "        \n",
    "        # Only keep the elements in arr that also exist in target\n",
    "        new_arr = [my_dict[val] for val in arr if val in my_dict]\n",
    "\n",
    "        # Find the length of LIS in new_arr\n",
    "        lis = []\n",
    "        for x in new_arr:\n",
    "            idx = self.binary_search(lis, x)\n",
    "            if idx == len(lis):\n",
    "                lis.append(x)\n",
    "            else:\n",
    "                lis[idx] = x\n",
    "\n",
    "        return len(target) - len(lis)\n",
    "    \n",
    "    def binary_search(self, lis, x):\n",
    "        l, r = 0, len(lis) \n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if lis[mid] < x:\n",
    "                l = mid +1\n",
    "            else:\n",
    "                r = mid \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        v_idx = {v: i for i, v in enumerate(target)}\n",
    "        nums = [v_idx[v] for v in arr if v in v_idx]\n",
    "        n = len(nums)\n",
    "        min_end = [-1]\n",
    "        for v in nums:\n",
    "            i = bisect.bisect_left(min_end, v)\n",
    "            if i < len(min_end):\n",
    "                min_end[i] = min(min_end[i], v)\n",
    "            else:\n",
    "                min_end.append(v)\n",
    "        return len(target) - len(min_end) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(target)):\n",
    "            dic[target[i]] = i\n",
    "        array = []\n",
    "        for a in arr:\n",
    "            if a in dic:\n",
    "                array.append(dic[a])\n",
    "        new = []\n",
    "        for a in array:\n",
    "            if not new or new[-1] < a:\n",
    "                new.append(a)\n",
    "            else:\n",
    "                idx = bisect_left(new, a)\n",
    "                new[idx] = a\n",
    "        return len(target) - len(new)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LongestIncreasingSubsequence:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def definitely_increase(nums):\n",
    "        # 最长单调递增子序列（严格上升）\n",
    "        dp = []\n",
    "        for num in nums:\n",
    "            i = bisect.bisect_left(dp, num)\n",
    "            if 0 <= i < len(dp):\n",
    "                dp[i] = num\n",
    "            else:\n",
    "                dp.append(num)\n",
    "        return len(dp)\n",
    "\n",
    "    @staticmethod\n",
    "    def definitely_not_reduce(nums):\n",
    "        # 最长单调不减子序列（不降）\n",
    "        dp = []\n",
    "        for num in nums:\n",
    "            i = bisect.bisect_right(dp, num)\n",
    "            if 0 <= i < len(dp):\n",
    "                dp[i] = num\n",
    "            else:\n",
    "                dp.append(num)\n",
    "        return len(dp)\n",
    "\n",
    "    def definitely_reduce(self, nums):\n",
    "        # 最长单调递减子序列（严格下降）\n",
    "        nums = [-num for num in nums]\n",
    "        return self.definitely_increase(nums)\n",
    "\n",
    "    def definitely_not_increase(self, nums):\n",
    "        # 最长单调不增子序列（不升）\n",
    "        nums = [-num for num in nums]\n",
    "        return self.definitely_not_reduce(nums)\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        ind = {num: i for i, num in enumerate(target)}\n",
    "        lst = [ind[num] for num in arr if num in ind]\n",
    "        return len(target) - LongestIncreasingSubsequence().definitely_increase(lst)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        n, m = len(target), len(arr)\n",
    "        mapping = {target[i]: i for i in range(n)}\n",
    "        indices = [mapping[arr[i]] for i in range(m) if arr[i] in mapping]\n",
    "        indices_length = len(indices)\n",
    "        max_len, g = 0, [float('inf')] * (indices_length + 1)\n",
    "\n",
    "        for i in range(indices_length):\n",
    "            t = indices[i]\n",
    "            l, r = 0, indices_length\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if g[mid] < t:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            clen = r + 1\n",
    "            max_len = max(max_len, clen)\n",
    "            g[clen] = min(g[clen], t)\n",
    "\n",
    "        return n - max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        m, n = len(target), len(arr)\n",
    "        p = {}\n",
    "        for i, num in enumerate(target):\n",
    "            p[num] = i\n",
    "\n",
    "        tmp = []\n",
    "        for num in arr:\n",
    "            if num in p:\n",
    "                tmp.append(p[num])\n",
    "        d = []\n",
    "        for num in tmp:\n",
    "            if not d or num > d[-1]:\n",
    "                d.append(num)\n",
    "            else:\n",
    "                idx = bisect.bisect_left(d, num)\n",
    "                d[idx] = num\n",
    "        # print(d)\n",
    "        return m - len(d)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 因为target元素互不相同，用哈希表构建target元素和下标之间的映射\n",
    "        # 将arr中的target元素映射为下标，因为要使得target是arr的一个子序列，\n",
    "        # 那么映射后下标肯定要从0到len(target)-1\n",
    "        # 所以算出已有的最长递增子序列，则已有的这些是不用添加了，只需要再添加缺少的就行\n",
    "        dictA = dict()\n",
    "        for i,t in enumerate(target):\n",
    "            dictA[t] = i   \n",
    "        arr_map = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in dictA:\n",
    "                arr_map.append(dictA[arr[i]])\n",
    "        \n",
    "        longest = self.lengthOfLIS(arr_map)\n",
    "        return len(target) - longest\n",
    "\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        res = [nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>res[-1]:\n",
    "                res.append(nums[i])\n",
    "            else:\n",
    "                idx = bisect_left(res, nums[i])\n",
    "                res[idx] = nums[i]\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# LIS problem : Longest Increasing Subsequence\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        def LIS(nums):\n",
    "            # dp[i] : the smallest ending number of subsequence that has length i+1\n",
    "            dp = []\n",
    "            for x in nums:\n",
    "                idx = bisect_left(dp,x)\n",
    "                if idx == len(dp):\n",
    "                    dp.append(x)\n",
    "                else:\n",
    "                    dp[idx] = x\n",
    "            return len(dp)\n",
    "\n",
    "        M = {x:i for i,x in enumerate(target)}\n",
    "        C = [M[x] for x in arr if x in M]\n",
    "        return len(target) - LIS(C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 将target中的数字映射到其索引\n",
    "        index_map = {num: i for i, num in enumerate(target)}\n",
    "        \n",
    "        # 将arr转换为其在target中的索引表示\n",
    "        # 只保留target中存在的数字\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if num in index_map:\n",
    "                stack.append(index_map[num])\n",
    "        \n",
    "        # 在stack中找最长递增子序列\n",
    "        lis = []\n",
    "        for num in stack:\n",
    "            idx = bisect.bisect_left(lis, num)\n",
    "            if idx == len(lis):\n",
    "                lis.append(num)\n",
    "            else:\n",
    "                lis[idx] = num\n",
    "        \n",
    "        # 返回需要插入的元素数量\n",
    "        return len(target) - len(lis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\r\n",
    "        target_index = dict()\r\n",
    "        for i in range(len(target)):\r\n",
    "            target_index[target[i]] = i\r\n",
    "        actual = []\r\n",
    "        for n in arr:\r\n",
    "            if n in target_index:\r\n",
    "                actual.append(target_index[n])\r\n",
    "        # 如果actual中可以被用来顶一顶组成target，要求index能组成LIS，剩余部分都得补\r\n",
    "        # n^2 LIS 超时\r\n",
    "        # def LIS(nums):\r\n",
    "        #     n = len(nums)\r\n",
    "        #     if n == 0:\r\n",
    "        #         return 0\r\n",
    "        #     dp = [1] * n\r\n",
    "        #     for i in range(n):\r\n",
    "        #         for j in range(i):\r\n",
    "        #             if nums[i] > nums[j]:\r\n",
    "        #                 dp[i] = max(dp[i], dp[j] + 1)\r\n",
    "        #     return max(dp)\r\n",
    "        def LIS(nums):\r\n",
    "            if len(nums) == 0:\r\n",
    "                return 0\r\n",
    "            d = []\r\n",
    "            for n in nums:\r\n",
    "                if not d or n > d[-1]:\r\n",
    "                    d.append(n)\r\n",
    "                else:\r\n",
    "                    l, r = 0, len(d) - 1\r\n",
    "                    loc = r\r\n",
    "                    while l <= r:\r\n",
    "                        mid = (l + r) // 2\r\n",
    "                        if d[mid] >= n:\r\n",
    "                            loc = mid\r\n",
    "                            r = mid - 1\r\n",
    "                        else:\r\n",
    "                            l = mid + 1\r\n",
    "                    d[loc] = n\r\n",
    "            return len(d)\r\n",
    "        return len(target) - LIS(actual)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        target = [5,1,3], arr = [9,4,2,3,4]\n",
    "        :param target:\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for k,v in enumerate(target):\n",
    "            m1[v] = k\n",
    "        arr2 = []\n",
    "        for i in arr:\n",
    "            if i not in m1:\n",
    "                continue\n",
    "            arr2.append(m1.get(i, -1))\n",
    "        dp = []\n",
    "        for i in arr2:\n",
    "            if not dp or i > dp[-1]:\n",
    "                dp.append(i)\n",
    "            else:\n",
    "                tag = bisect_left(dp, i)\n",
    "                if tag == len(dp):\n",
    "                    tag -= 1\n",
    "                dp[tag] = i\n",
    "\n",
    "        return len(target) - len(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict(zip(target, range(len(target))))\n",
    "        arr = list(map(lambda x: d[x], filter(lambda x: x in d, arr)))\n",
    "\n",
    "        dp = [-inf]\n",
    "        for a in arr:\n",
    "            if a > dp[-1]: dp.append(a)\n",
    "            else: dp[bisect_left(dp, a)] = a\n",
    "        return len(target) - (len(dp) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        f[0] = -1\n",
    "        idx = 1\n",
    "        for x in arr:\n",
    "            if x not in d:\n",
    "                continue\n",
    "            i = d[x]\n",
    "            if i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 1\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "\t\ttarget_dict = {}\n",
    "\t\tfor index, data in enumerate(target):\n",
    "\t\t\ttarget_dict[data] = index\n",
    "\t\tarr_copy = copy.deepcopy(arr)\n",
    "\t\tfor index, data in enumerate(arr):\n",
    "\t\t\tposition = target_dict.get(data, -1)\n",
    "\t\t\tarr_copy[index] = position\n",
    "\t\tif max(arr_copy) == -1:\n",
    "\t\t\treturn len(target)\n",
    "\t\t# 遍历数组\n",
    "\t\ttest = self.lengthOfLIS_2(arr_copy)\n",
    "\t\treturn len(target) - test\n",
    "\t\n",
    "\tdef lengthOfLIS_2(self, nums):\n",
    "\t\tnums_copy = []\n",
    "\t\tfor data in nums:\n",
    "\t\t\tif data != -1:\n",
    "\t\t\t\tnums_copy.append(data)\n",
    "\t\ttailor = [0 for i in range(len(nums_copy))]\n",
    "\t\tlength = 1\n",
    "\t\ttailor[0] = nums_copy[0]\n",
    "\t\tfor num in nums_copy[1:]:\n",
    "\t\t\tindex = bisect.bisect_left(tailor[0: length], num)\n",
    "\t\t\ttailor[index] = num\n",
    "\t\t\tif index == length:\n",
    "\t\t\t\tlength += 1\n",
    "\t\treturn length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        f[0] = -1\n",
    "        idx = 1\n",
    "        for x in arr:\n",
    "            i = d.get(x)\n",
    "            if i is None:\n",
    "                continue\n",
    "            if i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 1\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        idx = 0\n",
    "        for x in arr:\n",
    "            i = d.get(x)\n",
    "            if i is None:\n",
    "                continue\n",
    "            if idx == 0 or i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 0\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        rs = []\n",
    "        maxlen = 0\n",
    "        target_dict = dict(zip(target, list(range(len(target)))))\n",
    "        arr_ind = []\n",
    "        rs = []\n",
    "        maxlen = 0\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in target_dict.keys():\n",
    "                continue\n",
    "            val = target_dict[arr[i]]\n",
    "            ind = bisect.bisect_left(rs,val)\n",
    "            if ind==len(rs):\n",
    "                rs.append(val)\n",
    "            else:\n",
    "                rs[ind]=val\n",
    "        return len(target)-len(rs)\n",
    "        # for i in range(len(arr)):\n",
    "        #     if arr[i] in target_dict.keys():\n",
    "        #         arr_ind.append(target_dict[arr[i]])\n",
    "        #         rs.append(1)\n",
    "        #     else:\n",
    "        #         arr_ind.append(-1)\n",
    "        #         rs.append(0)\n",
    "        #         continue\n",
    "        #     for j in range(i):\n",
    "        #         if arr_ind[j]>=0 and arr_ind[i]>arr_ind[j]:\n",
    "        #             rs[i] = max(rs[i],rs[j]+1)\n",
    "        #     maxlen = max(maxlen,rs[i])\n",
    "            \n",
    "        # target_dict = dict(zip(target,[[] for _ in range(len(target))]))\n",
    "        # for i in range(len(arr)):\n",
    "        #     if arr[i] in target_dict.keys():\n",
    "        #         target_dict[arr[i]].append(i)\n",
    "\n",
    "        # for i in range(len(target)):\n",
    "        #     indicies = target_dict[target[i]]\n",
    "        #     rs.append([])\n",
    "        #     for j in indicies:\n",
    "        #         if arr[j]==target[i]:\n",
    "        #             rs[i].append([1,j])\n",
    "        #             for k in range(i):\n",
    "        #                 for l in rs[k]:\n",
    "        #                     if l[1]<j and l[0]+1>rs[i][-1][0]:\n",
    "        #                         rs[i][-1][0] = l[0]+1\n",
    "        #             maxlen = max(maxlen,rs[i][-1][0])\n",
    "        return len(target)-maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "\t\ttarget_dict = {}\n",
    "\t\tfor index, data in enumerate(target):\n",
    "\t\t\ttarget_dict[data] = index\n",
    "\t\tarr_copy = copy.deepcopy(arr)\n",
    "\t\tfor index, data in enumerate(arr):\n",
    "\t\t\tposition = target_dict.get(data, -1)\n",
    "\t\t\tarr_copy[index] = position\n",
    "\t\tif max(arr_copy) == -1:\n",
    "\t\t\treturn len(target)\n",
    "\t\tdp = [1] * len(arr_copy)\n",
    "\t\t# 遍历数组\n",
    "\t\ttest = self.lengthOfLIS(arr_copy)\n",
    "\t\t# for i in range(len(arr_copy)):\n",
    "\t\t# \tfor j in range(i):\n",
    "\t\t# \t\tif arr_copy[i] > arr_copy[j] != -1:\n",
    "\t\t# \t\t\tdp[i] = max(dp[i], dp[j] + 1)\n",
    "\t\t# print(dp, )\n",
    "\t\treturn len(target) - test\n",
    "\t\n",
    "\tdef lengthOfLIS(self, nums):\n",
    "\t\tif not nums:\n",
    "\t\t\treturn 0\n",
    "\t\t\n",
    "\t\t# 创建一个辅助数组tails，用于存储递增子序列的尾部元素\n",
    "\t\ttails = [0] * len(nums)\n",
    "\t\t# 初始化最长递增子序列的长度为1\n",
    "\t\tlength = 0\n",
    "\t\t\n",
    "\t\t# 遍历输入数组\n",
    "\t\tfor num in nums:\n",
    "\t\t\tif num == -1:\n",
    "\t\t\t\tcontinue\n",
    "\t\t\t# 使用二分查找在tails数组中找到适合插入的位置\n",
    "\t\t\tleft, right = 0, length - 1\n",
    "\t\t\twhile left <= right:\n",
    "\t\t\t\tmid = (left + right) // 2\n",
    "\t\t\t\tif tails[mid] < num:\n",
    "\t\t\t\t\tleft = mid + 1\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tright = mid - 1\n",
    "\t\t\t\n",
    "\t\t\t# 将num插入到tails数组中，如果num比当前递增子序列的尾部元素都大，就追加到最后\n",
    "\t\t\ttails[left] = num\n",
    "\t\t\t# 如果插入位置是当前递增子序列的尾部，递增子序列长度加1\n",
    "\t\t\tif left == length:\n",
    "\t\t\t\tlength += 1\n",
    "\t\t\n",
    "\t\treturn length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        idx = 0\n",
    "        for x in arr:\n",
    "            i = d.get(x)\n",
    "            if i is None:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            if l >= idx:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "            else:\n",
    "                f[l] = i\n",
    "        return n - idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        D = {i:idx for idx,i in enumerate(target)}\n",
    "        L = []\n",
    "        for i in arr:\n",
    "            if i in D:L.append(D[i])\n",
    "        if not L:return len(target)\n",
    "        Res = [L[0]]\n",
    "        for i in L[1:]:\n",
    "            if i > Res[-1]:Res.append(i)\n",
    "            else:\n",
    "                Res[bisect_left(Res,i)] = i\n",
    "        return len(target)-len(Res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, t: List[int], a: List[int]) -> int:\n",
    "        s = {t[j]:j for j in range(len(t))}\n",
    "        a = [s[j] for j in a if j in s]\n",
    "    \n",
    "        b = []\n",
    "        for j in a[:]:\n",
    "            i = bisect_left(b, j)\n",
    "            if i==len(b):\n",
    "                b.append(j)\n",
    "            else:\n",
    "                b[i] = j \n",
    "        return len(t) - len(b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,n):\n",
    "        self.F = [0] * 4*n\n",
    "    \n",
    "    def update(self,o,l,r,a,b,mx):\n",
    "        if l == r:self.F[o] = mx;return\n",
    "        if a <= l and r <= b:\n",
    "            self.F[o] = max(self.F[o],mx)\n",
    "            return\n",
    "        m = (l+r)>>1\n",
    "        if a <= m:\n",
    "            self.update(2*o,l,m,a,b,mx)\n",
    "        if m+1 <= b:\n",
    "            self.update(2*o+1,m+1,r,a,b,mx)\n",
    "        self.F[o] = max(self.F[2*o],self.F[2*o+1])\n",
    "        return\n",
    "\n",
    "    def query(self,o,l,r,a,b):\n",
    "        if l == r or a <= l and r <= b:return self.F[o]\n",
    "        res = 0\n",
    "        m = (l+r)>>1\n",
    "        if m >= a:res = max(res,self.query(2*o,l,m,a,b))\n",
    "        if m+1 <= b:res = max(self.query(2*o+1,m+1,r,a,b),res)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        D = {i:idx for idx,i in enumerate(target)}\n",
    "        n = len(target)\n",
    "        Tr = SegTree(n)\n",
    "        for idx,i in enumerate(arr):\n",
    "            if i not in D:continue\n",
    "            if D[i] == 0:mx = 1\n",
    "            else:mx = Tr.query(1,0,n-1,0,D[i]-1)+1\n",
    "            Tr.update(1,0,n-1,D[i],D[i],mx)\n",
    "        return n - Tr.F[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        my_dict = {}\n",
    "        for i, x in enumerate(target):\n",
    "            my_dict[x] = i\n",
    "        \n",
    "        def binary_search(lis, x):\n",
    "            left, right = 0, len(lis)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if lis[mid] < x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        \n",
    "        lis = []\n",
    "        my_set=set(target)\n",
    "        for x in arr:\n",
    "            if x not in my_set:\n",
    "                continue\n",
    "            x = my_dict[x]\n",
    "            my_loc = binary_search(lis, x)\n",
    "            if my_loc == len(lis):\n",
    "                lis.append(x)\n",
    "            else:\n",
    "                lis[my_loc] = x\n",
    "\n",
    "        return len(target) - len(lis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,n,L):\n",
    "        self.F = [0] * (4*n)\n",
    "        self.lz = [0] * (4*n)\n",
    "        self.n = n\n",
    "        self.L = L\n",
    "\n",
    "    def maintain(self,o):\n",
    "        self.F[o] = max(self.F[2*o],self.F[2*o+1])\n",
    "        return\n",
    "\n",
    "    def build(self,o,l,r):\n",
    "        if l == r-1:\n",
    "            self.F[o] = self.L[l]\n",
    "            return\n",
    "        m = (l+r)//2\n",
    "        self.build(2*o,l,m)\n",
    "        self.build(2*o+1,m,r)\n",
    "        self.maintain(o)        \n",
    "        return\n",
    "        \n",
    "\n",
    "    def update(self,o,l,r,a,b,v):\n",
    "        if l == r-1:self.F[o] = max(self.F[o],v);return\n",
    "        elif a <= l and r <= b:\n",
    "            if v > self.F[o]:\n",
    "                self.F[o] = v\n",
    "                self.lz[o] = v\n",
    "            return\n",
    "        m = (l+r)//2\n",
    "        if self.lz[o]:\n",
    "            if v > self.F[2*o]:\n",
    "                self.F[2*o] = v\n",
    "                self.lz[2*o] = v\n",
    "            if v > self.F[2*o+1]:\n",
    "                self.F[2*o+1] = v\n",
    "                self.lz[2*o+1] = v\n",
    "            self.lz[o] = 0\n",
    "        if m > a: \n",
    "            self.update(2*o,l,m,a,b,v)\n",
    "        if m < b:\n",
    "            self.update(2*o+1,m,r,a,b,v)\n",
    "        self.maintain(o)\n",
    "        return\n",
    "    \n",
    "    def query(self,o,l,r,a,b):\n",
    "        res = 0\n",
    "        if l == r or (a <= l and r <= b):return self.F[o]\n",
    "        m = (l+r)//2   \n",
    "        if m > a:\n",
    "            res = max(res,self.query(2*o,l,m,a,b))\n",
    "        if m < b:\n",
    "            res = max(res,self.query(2*o+1,m,r,a,b))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        D = {i:idx for idx,i in enumerate(target)}\n",
    "        n = len(target)\n",
    "        Tr = SegTree(n,[0]*n)\n",
    "        for idx,i in enumerate(arr):\n",
    "            if i not in D:continue\n",
    "            if D[i] == 0:mx = 1\n",
    "            else:mx = Tr.query(1,0,n,0,D[i])+1\n",
    "            Tr.update(1,0,n,D[i],D[i]+1,mx)\n",
    "        return n - Tr.F[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2023-09-22 15:52:53\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        s = set(target)\n",
    "\n",
    "        mp = {v: i for i, v in enumerate(target)}\n",
    "        a = []\n",
    "\n",
    "        for x in arr:\n",
    "            if x in s:\n",
    "                a.append(mp[x])\n",
    "\n",
    "        # print(a)\n",
    "        n = len(target)\n",
    "\n",
    "        def lcs(a):\n",
    "            q = []\n",
    "            for x in a:\n",
    "                if not q or x > q[-1]:\n",
    "                    q.append(x)\n",
    "                else:\n",
    "                    i = bisect_left(q, x)\n",
    "                    q[i] = x\n",
    "            return len(q)\n",
    "\n",
    "        return n - lcs(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        t=dict([(n,i) for i,n in enumerate(target)])\n",
    "        aa=[t[x] for x in arr if x in t]\n",
    "        a=[100001]*len(aa)\n",
    "        for n in aa:a[bisect.bisect_left(a,n)]=n\n",
    "        return len(target)-len([x for x in a if x!=100001])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        arr = []\n",
    "        mo = grid[0][0] % x\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] % x != mo:\n",
    "                    return -1\n",
    "                arr.append(grid[i][j])\n",
    "        arr = sorted(arr)\n",
    "        zhong = arr[m*n//2]\n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            res += abs(arr[i]-zhong) / x\n",
    "        return int(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        arr = [item for sublist in grid for item in sublist]\n",
    "        arr.sort()\n",
    "        mid = arr[len(arr)//2]\n",
    "\n",
    "        ans = 0\n",
    "        for v in arr:\n",
    "            if abs(v-mid)%x!=0:\n",
    "                return -1\n",
    "            ans += abs(v-mid)//x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        v = [t for g in grid for t in g]\n",
    "        n = len(v)\n",
    "        m = v[0] % x\n",
    "        if sum(1 for t in v if t % x != m) > 0:\n",
    "            return -1\n",
    "        v.sort()\n",
    "        t = v[n // 2]\n",
    "        return sum(abs(a - t) // x for a in v)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        l = []\n",
    "        for row in grid:\n",
    "            l += row\n",
    "        l.sort()\n",
    "        m = l[0]\n",
    "        for i in range(len(l)):\n",
    "            if (l[i] - m) % x:\n",
    "                return -1\n",
    "            l[i] = (l[i] - m) // x\n",
    "        v = sum(l)\n",
    "        t = v\n",
    "        for i in range(1, len(l)):\n",
    "            d = l[i] - l[i - 1]\n",
    "            t += d * (2 * i - len(l))\n",
    "            v = min(v, t)\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        nums = []\n",
    "        for g in grid:\n",
    "            for y in g:\n",
    "                nums.append(y)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        mid = nums[n // 2]\n",
    "        if any(y % x != nums[0] % x for y in nums):\n",
    "            return -1\n",
    "        ans = 0\n",
    "        for y in nums:\n",
    "            ans += abs(y - mid) // x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        nums = [a for b in grid for a in b]\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        target = nums[n//2]\n",
    "        res = 0\n",
    "        for ele in nums:\n",
    "            if (ele - target) % x:\n",
    "                return -1\n",
    "            res += abs(target - ele) // x\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        line, col, ret, li = len(grid), len(grid[0]), 0, []\n",
    "        for i in grid:\n",
    "            li.extend(i)\n",
    "        li.sort()\n",
    "        mid = li[len(li) // 2]\n",
    "        for v in li:\n",
    "            if abs(mid - v) % x:\n",
    "                return -1\n",
    "            ret += abs(mid - v) // x\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        flat_grid = [grid[i][j] for i in range(m) for j in range(n)]\n",
    "        \n",
    "        # Check if it's possible to make the grid uni-value\n",
    "        remainder = flat_grid[0] % x\n",
    "        for num in flat_grid:\n",
    "            if num % x != remainder:\n",
    "                return -1\n",
    "        \n",
    "        # Calculate the number of operations\n",
    "        flat_grid.sort()\n",
    "        median = flat_grid[len(flat_grid) // 2]\n",
    "        operations = 0\n",
    "        \n",
    "        for num in flat_grid:\n",
    "            operations += abs(num - median) // x\n",
    "        \n",
    "        return operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        nums = [0] * (m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a,b = divmod(grid[i][j] - grid[0][0], x)\n",
    "                if b:\n",
    "                    return -1\n",
    "                nums[i*n+j] = a\n",
    "\n",
    "        nums.sort()\n",
    "        mid = nums[m*n>>1]\n",
    "        return sum(num - mid if num > mid else mid - num for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        v = [t for g in grid for t in g]\n",
    "        n = len(v)\n",
    "        m = v[0] % x\n",
    "        if sum(1 for t in v if t % x != m) > 0:\n",
    "            return -1\n",
    "        v.sort()\n",
    "        t = v[(n - 1) // 2]\n",
    "        return sum(abs(a - t) // x for a in v)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        lst = []\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                lst.append(grid[i][j])\n",
    "        lst.sort()\n",
    "        n = len(lst)\n",
    "        a = lst[n//2]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if abs(a-lst[i]) % x !=0:\n",
    "                return -1\n",
    "            else:\n",
    "                ans+=(abs(a-lst[i]))//x\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        m,n,mod = len(grid),len(grid[0]),grid[0][0]%x\n",
    "        arr = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] % x != mod:return -1\n",
    "                arr.append(grid[i][j])\n",
    "\n",
    "        arr.sort()\n",
    "        ans = 0\n",
    "        for i in arr:\n",
    "            ans += abs(i-arr[n*m//2])//x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        m,n,p = len(grid),len(grid[0]),grid[0][0]%x\n",
    "        arr = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] % x != p:return -1\n",
    "                arr.append(grid[i][j])\n",
    "        \n",
    "        arr.sort()\n",
    "        ans = 0\n",
    "        for i in arr:\n",
    "            ans =ans + abs(i - arr[n*m//2])//x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        mod=grid[0][0]%x\n",
    "        a=[]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]%x!=mod:\n",
    "                    return -1\n",
    "                a.append(grid[i][j]//x)\n",
    "        a.sort()\n",
    "        x=len(a)//2\n",
    "        ans=0\n",
    "        for i in a:\n",
    "            ans+=abs(i-a[x])\n",
    "        return ans        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        nums = [a for b in grid for a in b]\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        target = nums[n//2]\n",
    "        res = 0\n",
    "        for ele in nums:\n",
    "            if (ele - target) % x:\n",
    "                return -1\n",
    "            res += abs(target - ele) // x\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 排序+贪心+中位数\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        nums = []\n",
    "        for g in grid:\n",
    "            nums.extend(g)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if (nums[i + 1] - nums[i]) % x != 0:\n",
    "                return -1\n",
    "\n",
    "        mid = nums[n // 2]\n",
    "        return sum(abs(num - mid) // x for num in nums)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        s = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (grid[i][j] - grid[0][0]) % x:\n",
    "                    return -1\n",
    "                s.append(grid[i][j])\n",
    "        s.sort()\n",
    "        mid = s[len(s) // 2]\n",
    "        return sum(abs(v - mid) // x for v in s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        nums = []\n",
    "        for row in grid:\n",
    "            nums += row\n",
    "        nums.sort()\n",
    "\n",
    "        n = len(nums)\n",
    "        median = nums[n // 2]\n",
    "\n",
    "        res, rr = divmod(abs(nums[0] - median), x)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            q, r = divmod(abs(nums[i] - median), x)\n",
    "            if r != rr:\n",
    "                return -1\n",
    "\n",
    "            res += q\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x2: int) -> int:\n",
    "        e=[y for x in grid for y in x]\n",
    "        e.sort()\n",
    "        n=len(e)\n",
    "        c=-1\n",
    "        c=e[0]\n",
    "        for x in e:\n",
    "            if abs(x-c)%x2!=0:\n",
    "                return -1\n",
    "        if n%2:\n",
    "           c=e[n//2]\n",
    "        else:\n",
    "           c=(e[n//2-1]+e[n//2])//2     \n",
    "        print(c)\n",
    "        res =0\n",
    "        for x1 in e:\n",
    "            res+=abs(x1-c)/x2    \n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        ls = []\n",
    "        r, c = len(grid), len(grid[0])\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                ls.append(grid[i][j])\n",
    "\n",
    "        ls.sort()\n",
    "        tar = ls[len(ls) // 2]\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for e in ls:\n",
    "            div, mod = divmod(abs(tar - e), x)\n",
    "            if mod != 0:\n",
    "                return -1\n",
    "            ans += div\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        nums = []\n",
    "        for row in grid:\n",
    "            nums += row\n",
    "        nums.sort()\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        median = nums[n // 2]\n",
    "\n",
    "        res, rr = divmod(abs(nums[0] - median), x)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            q, r = divmod(abs(nums[i] - median), x)\n",
    "            if r != rr:\n",
    "                return -1\n",
    "                \n",
    "            res += q\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        line, col, ret, li = len(grid), len(grid[0]), 0, []\n",
    "        for i in grid:\n",
    "            li.extend(i)\n",
    "        li.sort()\n",
    "        mid = li[len(li) // 2]\n",
    "        for v in li:\n",
    "            if abs(mid - v) % x:\n",
    "                return -1\n",
    "            ret += abs(mid - v) // x\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        row=len(grid)\n",
    "        col=len(grid[0])\n",
    "        res=0\n",
    "        num_list=[]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                num_list.append(grid[i][j])\n",
    "        num_list.sort()\n",
    "        mid=num_list[len(num_list)//2]\n",
    "        for v in num_list:\n",
    "            if abs(v-mid)%x:\n",
    "                return -1\n",
    "            else:\n",
    "                res+=abs(v-mid)//x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        remain = grid[0][0] % x\n",
    "\n",
    "        ans = 0\n",
    "        times = []\n",
    "        for a in chain.from_iterable(grid):\n",
    "            time, rest = divmod(a, x)\n",
    "            if rest != remain:\n",
    "                return -1\n",
    "            times.append(time)\n",
    "        # 寻找times的中位数\n",
    "        target = round(median(times))\n",
    "        return int(sum(abs(t - target) for t in times))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        res = 0\n",
    "        l = []\n",
    "        for g in grid:\n",
    "            l.extend(g)\n",
    "        l.sort()\n",
    "        mid = l[len(l)//2]\n",
    "        for v in l:\n",
    "            if abs(mid - v) % x:\n",
    "                return -1\n",
    "            res += abs(mid - v) // x\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, grid, x):\r\n",
    "        line, col, ret, li = len(grid), len(grid[0]), 0, []\r\n",
    "        for i in grid:\r\n",
    "            li.extend(i)\r\n",
    "        li.sort()\r\n",
    "        mid = li[len(li) // 2]\r\n",
    "        for v in li:\r\n",
    "            if abs(mid - v) % x:\r\n",
    "                return -1\r\n",
    "            ret += abs(mid - v) // x\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        mod = grid[0][0] % x\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for row in grid:\n",
    "            for num in row:\n",
    "                d, m = divmod(num, x)\n",
    "                if m != mod:\n",
    "                    return -1\n",
    "                cnt[d] += 1\n",
    "        \n",
    "        n = (len(grid) * len(grid[0]) + 1) // 2\n",
    "        c = 0\n",
    "        for key in sorted(cnt.keys()):\n",
    "            c += cnt[key]\n",
    "            if c >= n:\n",
    "                break\n",
    "        return sum(v * abs(k - key) for k, v in cnt.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        g = []\n",
    "        for l in grid:\n",
    "            g += l\n",
    "        if len(g) == 1:\n",
    "            return 0\n",
    "        temp = g[0] % x\n",
    "        for num in g:\n",
    "            if num % x != temp:\n",
    "                return -1\n",
    "        g.sort()\n",
    "        n = len(g)\n",
    "        key = g[n//2]\n",
    "        return sum(abs(num - key)//x for num in g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid, x):\n",
    "        grids = []\n",
    "        for i in grid:\n",
    "            grids += i\n",
    "        grid_ = list(set(grids))\n",
    "        if len(grid_) == 1:\n",
    "            return 0\n",
    "        grids.sort()\n",
    "        base = grids[len(grids) // 2]\n",
    "        temp = 0\n",
    "        for i in grids:\n",
    "            if abs(base - i) % x == 0:\n",
    "                b = abs(base - i) // x\n",
    "                temp += b\n",
    "            else:\n",
    "                return -1\n",
    "        return temp  # 注意这里应该返回 temp 而不是 res，代码中的 res 未定义\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        target = grid[0][0]\n",
    "        nums = []\n",
    "        for i in range(m):\n",
    "            nums += grid[i]\n",
    "            for j in range(n):\n",
    "                if((grid[i][j]-target) % x != 0):\n",
    "                    return -1\n",
    "        nums.sort()\n",
    "        nums_cnt = m*n\n",
    "        if(nums_cnt % 2 == 1): \n",
    "            target = nums[m*n//2]\n",
    "            result = 0\n",
    "            for num in nums:\n",
    "                result += abs(num-target)//x\n",
    "        else:\n",
    "            target1 = nums[m*n//2-1]\n",
    "            target2 = nums[m*n//2]\n",
    "            r1, r2 = 0, 0\n",
    "            for num in nums:\n",
    "                r1 += abs(num-target1)//x\n",
    "                r2 += abs(num-target2)//x\n",
    "            result = min(r1,r2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        res,li,ret=0,[],0\n",
    "        for i in grid:\n",
    "            li+=i\n",
    "        n=len(li)\n",
    "        for v in li:\n",
    "            if (v-li[0])%x!=0: \n",
    "                return -1\n",
    "        li.sort(reverse=True)\n",
    "        res=0\n",
    "        for i in li:\n",
    "            res+=abs(i-li[n//2])//x\n",
    "\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        src = grid[0][0]\n",
    "        cnts = sorted(Counter(num - src for row in grid for num in row).items())\n",
    "        mid_cnt = (len(grid) * len(grid[0]))>>1\n",
    "        pre_cnt = 0  \n",
    "        mid = 0\n",
    "        find = False\n",
    "        for k,cnt in cnts:\n",
    "            if k % x:\n",
    "                return -1\n",
    "            pre_cnt += cnt \n",
    "            if not find and pre_cnt > mid_cnt:\n",
    "                mid = k\n",
    "                find = True\n",
    "        return sum((k-mid if k > mid else mid-k) * cnt for k, cnt in cnts) // x\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        remain = grid[0][0] % x\n",
    "\n",
    "        ans = 0\n",
    "        times = []\n",
    "        for a in chain.from_iterable(grid):\n",
    "            time, rest = divmod(a, x)\n",
    "            if rest != remain:\n",
    "                return -1\n",
    "            times.append(time)\n",
    "        # 寻找times的中位数\n",
    "        target = round(median(times))\n",
    "        return sum(abs(t - target) for t in times)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, grid: List[List[int]], x: int) -> int:\n",
    "        src = grid[0][0]\n",
    "        cnts = sorted(Counter(num - src for row in grid for num in row).items())\n",
    "        mid_cnt = (len(grid) * len(grid[0]))>>1\n",
    "        pre_cnt = 0  \n",
    "        mid = cnts[-1][0]\n",
    "        for k,cnt in cnts:\n",
    "            if k % x:\n",
    "                return -1\n",
    "            pre_cnt += cnt \n",
    "            if mid == cnts[-1][0] and pre_cnt > mid_cnt:\n",
    "                mid = k\n",
    "        return sum((k-mid if k > mid else mid-k) * cnt for k, cnt in cnts) // x\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        pre = [0]\n",
    "        ps = 0\n",
    "        for i in range(len(nums)):\n",
    "            ps+=nums[i]\n",
    "            pre.append(ps)\n",
    "        \n",
    "\n",
    "        res = []\n",
    "        for x in queries:\n",
    "            l,r = 0,len(nums)-1\n",
    "            while l<=r:\n",
    "                m = (l+r)//2\n",
    "                \n",
    "                if x<nums[m]:\n",
    "                    r = m-1\n",
    "                else:\n",
    "                    l = m+1\n",
    "                        \n",
    "            \n",
    "            #l = bisect_left(nums,x)\n",
    "            res.append (l*x-pre[l]-(len(nums)-l)*x+pre[-1]-pre[l])\n",
    "            #res.append(l)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        ans=[]\n",
    "        temp=list(accumulate(nums,initial=0))\n",
    "        n=len(temp)\n",
    "        for i in range(len(queries)):\n",
    "            idx=bisect_left(nums,queries[i])\n",
    "            ans.append((idx+1)*queries[i]-temp[idx]+(temp[-1]-temp[idx])-(n-idx)*queries[i])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        ans=[]\n",
    "        temp=list(accumulate(nums,initial=0))\n",
    "        n=len(temp)\n",
    "        for i in range(len(queries)):\n",
    "            idx=bisect_left(nums,queries[i])\n",
    "            ans.append((idx)*queries[i]-temp[idx]+(temp[-1]-temp[idx])-(n-idx-1)*queries[i])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        #前缀和\n",
    "        n = len(nums)\n",
    "        pre_sum = [0]*(n+1)\n",
    "        for idx in range(n):\n",
    "            pre_sum[idx+1] = pre_sum[idx]  + nums[idx]\n",
    "        ans = [0]*len(queries)\n",
    "        # print(pre_sum)\n",
    "        for idx , val in enumerate(queries):\n",
    "            #二分查找 因为加的是绝对值说有比 val的 小与等于的\n",
    "            i = bisect.bisect_left(nums, val)\n",
    "            ans[idx] = i*val - pre_sum[i] + pre_sum[-1] - pre_sum[i] - (n-i)*val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        ls = len(nums)\n",
    "        su = sum(nums)\n",
    "        nums.sort()\n",
    "        P = [0] + nums[::]\n",
    "        for i in range(ls):\n",
    "            P[i+1] += P[i]\n",
    "        # [1, 3, 6, 8]\n",
    "        # q[i] = (i * len(小于i) - su(小于i)) + (su(大于等于i) - i * len(大于等于i))\n",
    "        #      = i * (len(小于i) - len(大于等于i)) + (su(大于等于i) - su(小于i))\n",
    "        #      = i * (2 * len(小于i) - ls) + (su - 2 * su(小于i))\n",
    "        #      = i * (2 * pos - ls) + (su - 2 * P[pos])\n",
    "        # ※pos = bisect_left(nums, i)\n",
    "        # print(P)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            pos = bisect.bisect_left(nums, q)\n",
    "            # print(pos)\n",
    "            ans[i] = q * (2 * pos - ls) + (su - 2 * P[pos])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        pre = [0] + list(accumulate(nums))\n",
    "        ans = [0] * len(queries)\n",
    "        for i, x in enumerate(queries):\n",
    "            j = bisect_left(nums, x + 1)\n",
    "            ans[i] = (j * 2 - n) * x + pre[n] - pre[j] * 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        pre_cumsum = [0]+[*itertools.accumulate(nums)]\n",
    "        res=[]\n",
    "        for q in queries:\n",
    "            idx=bisect.bisect_left(nums,q)\n",
    "            res.append(q*idx-pre_cumsum[idx]+pre_cumsum[-1]-pre_cumsum[idx]-q*(len(nums)-idx))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        arr, n = sorted(nums), len(nums)\n",
    "        ret, psum = [], list(accumulate(arr, initial=0))\n",
    "        for q in queries:\n",
    "            i = bisect_right(arr, q)\n",
    "            ret.append(i * q - psum[i] + psum[n] - psum[i] - (n - i) * q)\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        x = [sum(nums) - n*nums[0]]\n",
    "        for i in range(1,n):\n",
    "            x.append( x[i-1] + (i - (n-i)) * (nums[i] - nums[i-1]))\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            if q <= nums[0]:\n",
    "                ans.append(x[0]+ n*(nums[0] -q))\n",
    "            elif q >= nums[-1]:\n",
    "                ans.append(x[-1] + n * (q - nums[-1]))\n",
    "            else:\n",
    "                id = bisect.bisect_left(nums, q)\n",
    "                if nums[id] == q:\n",
    "                    ans.append(x[id])\n",
    "                else:\n",
    "                    ans.append(x[id-1] + (id*2-n)*(q-nums[id-1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        ar = [0] + nums\n",
    "        ar.append(10 ** 9 + 10)\n",
    "        ar.sort()\n",
    "        n = len(ar)\n",
    "        f = [0] * n\n",
    "        for i in range(1, n): f[i] += f[i - 1] + ar[i]\n",
    "        res = []\n",
    "\n",
    "        def find(ar, target):\n",
    "            l, r = 0, len(ar) - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if ar[mid] >= target: r = mid\n",
    "                else: l = mid + 1\n",
    "            return l\n",
    "\n",
    "        for q in queries:\n",
    "            idx = find(ar, q)\n",
    "            res.append((idx - 1) * q - f[idx - 1] + (f[n - 2] - f[idx - 1]) - (n - 1 - idx) * q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        ln = len(nums)\n",
    "        lq = len(queries)\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        c = -1\n",
    "        a = []\n",
    "        for i in range(ln):\n",
    "            if i > 0:\n",
    "                a.append(nums[i] + a[i-1])\n",
    "            else:\n",
    "                a.append(nums[i])\n",
    "        for i in range(lq):\n",
    "            left = 0\n",
    "            right = ln-1\n",
    "            mid = (left+right)//2\n",
    "            while(left<=right):\n",
    "                if nums[mid]<=queries[i]:\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid-1\n",
    "                mid = (left+right)//2\n",
    "            c = mid\n",
    "            if c<0:\n",
    "                res.append(a[-1]-(ln-c-1)*queries[i])\n",
    "            else:\n",
    "                res.append(a[-1]-a[c]-(ln-c-1)*queries[i]+(c+1)*queries[i]-a[c])\n",
    "\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        #arr=[1,2,2,4,4,5]\n",
    "        #return [list(accumulate(arr)),bisect_left(arr,2),bisect_left(arr,3),bisect_right(arr,2),bisect_right(arr,3)]\n",
    "        nums.sort()\n",
    "        pre_sum=list(accumulate(nums))\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            idx=bisect_right(nums,q)\n",
    "            #buff.append((q,idx,idx*q,pre_sum[idx-1],pre_sum[-1],pre_sum[idx-1],q*(len(nums)-idx)))\n",
    "            left=pre_sum[idx-1] if idx>0 else 0\n",
    "            right=pre_sum[-1] - (pre_sum[idx-1] if idx>0 else 0)\n",
    "            ans.append(idx*q-left+right-q*(len(nums)-idx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        prefix = list(accumulate(nums, initial=0))\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        for i, x in enumerate(queries):\n",
    "            idx = bisect_left(nums, x)\n",
    "            \n",
    "            if idx == 0:\n",
    "                res[i] = prefix[-1] - n * x\n",
    "            elif idx == n:\n",
    "                res[i] = n * x - prefix[-1]\n",
    "            else:\n",
    "                res[i] = (\n",
    "                    x * idx - prefix[idx] + \n",
    "                    prefix[-1] - prefix[idx] - n * x + idx * x\n",
    "                )\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        m = sum(nums)\n",
    "        nums.sort()\n",
    "        su = [0]\n",
    "        for i in range(n):\n",
    "            su.append(nums[i]+su[-1])\n",
    "\n",
    "        \n",
    "        li = []\n",
    "        for q in queries:\n",
    "            t = bisect_left(nums,q)\n",
    "            li.append(m - 2*su[t]-(n-2*t)*q)\n",
    "        return li"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        m = len(nums)\n",
    "        nums.sort()\n",
    "        preSum = [0] * (m + 1)\n",
    "        for i in range(1, m + 1):\n",
    "            preSum[i] = preSum[i - 1] + nums[i - 1]\n",
    "        _sum = preSum[-1]\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            j = bisect.bisect_left(nums, queries[i])\n",
    "            ans[i] = (queries[i] * j - preSum[j]) + _sum - preSum[j] - queries[i] * (m - j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        # 数从小到大排序，求前缀和\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        for q in queries:\n",
    "            pivot = bisect_left(nums, q)\n",
    "            # 把数组分为两部分，左边 < q，右边 >= q\n",
    "            # 那么左半部分的和一定小于 q * 左半部分长度，同理右半部分的和一定大于等于 q * 右半部分长度\n",
    "            # 用前缀和可以 O(1) 时间求出两个部分的和\n",
    "            # 答案就是的差值 + 右边的差值\n",
    "            left = pivot * q\n",
    "            right = (n - pivot) * q\n",
    "            left_sum = acc[pivot]\n",
    "            right_sum = acc[n] - acc[pivot]\n",
    "            ans.append(left - left_sum + right_sum - right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        acmu = [nums[0]]\n",
    "        r = len(nums) - 1\n",
    "        for i in range(1, r+1):\n",
    "            acmu.append(acmu[-1] + nums[i])\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            index = self.binFind(nums, r, query)\n",
    "            if index in [-1, r]:\n",
    "                res.append(abs(query * (r+1) - acmu[-1]))\n",
    "            else:\n",
    "                res.append(\n",
    "                query * (index+1) - acmu[index] + acmu[-1] - acmu[index] - query * (r-index)\n",
    "            )\n",
    "        return res\n",
    "\n",
    "    def binFind(self, nums, r, query) -> int:\n",
    "        l, r = 0, r\n",
    "        while l < r:\n",
    "            mid = l + (r-l) // 2\n",
    "            num = nums[mid]\n",
    "            if num == query:\n",
    "                return mid\n",
    "            if num < query:\n",
    "                l = mid + 1\n",
    "            if num > query:\n",
    "                r = mid\n",
    "        return l if nums[l] < query else l-1\n",
    "\n",
    "# 1 3 6 8 \n",
    "# index = 1, q = 5    10 - 4 + 14 - 10\n",
    "# accm = 1 4 10 18\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        #arr=[1,2,2,4,4,5]\n",
    "        #return [list(accumulate(arr)),bisect_left(arr,2),bisect_left(arr,3),bisect_right(arr,2),bisect_right(arr,3)]\n",
    "        nums.sort()\n",
    "        pre_sum=list(accumulate(nums,initial=0))\n",
    "        ans=[]\n",
    "        buff=[]\n",
    "        for q in queries:\n",
    "            idx=bisect_left(nums,q)\n",
    "            left=pre_sum[idx]\n",
    "            right=pre_sum[-1] - left\n",
    "            ans.append(idx*q-left+right-q*(len(nums)-idx))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        l, res = [sum(nums) - nums[0] * len(nums)], []\n",
    "        for i in range(1, len(nums)):\n",
    "            l.append(l[-1] + (nums[i] - nums[i - 1]) * (2 * i - len(nums)))\n",
    "        for x in queries:\n",
    "            pos = bisect.bisect_right(nums, x)\n",
    "            if pos == 0:\n",
    "                res.append(l[0] + (nums[0] - x) * len(nums))\n",
    "            elif pos == len(nums):\n",
    "                res.append(l[-1] + (x - nums[-1]) * len(nums))\n",
    "            else:\n",
    "                res.append(l[pos - 1] + (l[pos] - l[pos - 1]) * (x - nums[pos - 1]) // (nums[pos] - nums[pos - 1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        def find_num(num):\n",
    "            left = 0\n",
    "            right = length-1\n",
    "            while True:\n",
    "                mid = (left+right)//2\n",
    "                if right-left==1:\n",
    "                    return mid\n",
    "                elif nums[mid]<num:\n",
    "                    left = mid                   \n",
    "                else:\n",
    "                    right = mid\n",
    "        result = []\n",
    "        length = len(nums)\n",
    "        length2 = len(queries)\n",
    "        nums.sort()\n",
    "        sum_nums = [nums[0]]*length\n",
    "        if length==1:\n",
    "            return [abs(i-nums[0])for i in queries]\n",
    "        for i in range(1,length):\n",
    "            sum_nums[i] = sum_nums[i-1] + nums[i]\n",
    "        for i in range(0,length2):\n",
    "            if nums[0] <= queries[i] <= nums[-1]:\n",
    "                num_index = bisect_right(nums,queries[i])-1\n",
    "                result.append((num_index+1)*queries[i]-sum_nums[num_index]+sum_nums[-1]-sum_nums[num_index]-(length-num_index-1)*queries[i])\n",
    "            else:\n",
    "                result.append(abs(length*queries[i]-sum_nums[-1]))        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        pfxs = list(accumulate(nums))\n",
    "        n = len(nums)\n",
    "        def cal(q):\n",
    "            first_max_or_eq_idx = bisect_left(nums,q)\n",
    "            if first_max_or_eq_idx >= n:\n",
    "                return q*n-pfxs[-1]\n",
    "            if nums[first_max_or_eq_idx] == queries:\n",
    "                return pfxs[-1]-q*n \n",
    "            less_cnt = first_max_or_eq_idx\n",
    "            more_cnt = n-less_cnt\n",
    "            return q*less_cnt - (pfxs[first_max_or_eq_idx]-nums[first_max_or_eq_idx])+(pfxs[-1]-pfxs[first_max_or_eq_idx]+nums[first_max_or_eq_idx])-q*more_cnt\n",
    "        return [cal(i) for i in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        pfxs = list(accumulate(nums))\n",
    "        n = len(nums)\n",
    "        def cal(q):\n",
    "            first_max_or_eq_idx = bisect_left(nums,q)\n",
    "            less_cnt = first_max_or_eq_idx\n",
    "            more_cnt = n-less_cnt\n",
    "            if less_cnt >= n:\n",
    "                return q*n-pfxs[-1]\n",
    "            if nums[first_max_or_eq_idx] == queries:\n",
    "                return pfxs[-1]-q*n \n",
    "            return q*less_cnt - (pfxs[first_max_or_eq_idx]-nums[first_max_or_eq_idx])+(pfxs[-1]-pfxs[first_max_or_eq_idx]+nums[first_max_or_eq_idx])-q*more_cnt\n",
    "        return [cal(i) for i in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        pfxs = list(accumulate(nums))\n",
    "        n = len(nums)\n",
    "        def cal(q):\n",
    "            first_max_or_eq_idx = bisect_left(nums,q)\n",
    "            less_cnt = first_max_or_eq_idx\n",
    "            more_cnt = n-less_cnt\n",
    "            if less_cnt >= n:\n",
    "                return q*n-pfxs[-1]\n",
    "            if nums[first_max_or_eq_idx] == queries:\n",
    "                return pfxs[-1]-q*n \n",
    "            \n",
    "            return q*(less_cnt-more_cnt)+2*(nums[first_max_or_eq_idx]-pfxs[first_max_or_eq_idx])+pfxs[-1]\n",
    "        return [cal(i) for i in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        prefix = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefix[i] = prefix[i - 1] + nums[i - 1]\n",
    "        ret = [0] * len(queries)\n",
    "        for i, query in enumerate(queries):\n",
    "            l = bisect_left(nums, query)\n",
    "            # r = bisect_right(nums, query)\n",
    "            ret[i] = prefix[n] - prefix[l] - prefix[l] - query * (n - l- l)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        # 前缀和\n",
    "        summ = [0]\n",
    "        for i in nums: summ.append(summ[-1] + i)\n",
    "\n",
    "        # 二分查找\n",
    "        def bisect(arr, q):\n",
    "            l, r = 0, len(arr)-1\n",
    "            while l<=r:\n",
    "                mid = (l+r)//2\n",
    "                if arr[mid] == q:  return mid\n",
    "                elif arr[mid] < q: l = mid + 1\n",
    "                else: r = mid - 1\n",
    "            return l\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        for q in queries:\n",
    "            idx = bisect(nums, q)\n",
    "            left = idx*q - summ[idx]\n",
    "            right = summ[n] - summ[idx]- (n-idx)*q\n",
    "            ret.append(left+right)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        sub = [0]*(n+1)\n",
    "        for i,num in enumerate(nums):\n",
    "            sub[i+1] = sub[i]+num\n",
    "        for x in queries:\n",
    "            a = bisect_left(nums,x)\n",
    "            res.append(a*x-sub[a]+sub[-1]-sub[a]-(n-a)*x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(1, n+1):\n",
    "            presum[i] = presum[i-1] + nums[i-1]\n",
    "\n",
    "        def getans(k):\n",
    "            ans = 0\n",
    "            if nums[0] >= k:\n",
    "                return presum[n] - k * n\n",
    "            if nums[-1] <= k:\n",
    "                return k * n - presum[n]\n",
    "\n",
    "            l, r = 0, n-1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if nums[mid] >= k:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            \n",
    "            # 找到第一个>=k的位置\n",
    "            # 0-l-1需要加l-n-1需要-\n",
    "            return l * k - presum[l] + presum[n] - presum[l] - (n - l) * k\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(getans(q))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            presum[i] = presum[i-1] + nums[i-1] \n",
    "\n",
    "        def get(q):\n",
    "            if nums[0] >= q:\n",
    "                return presum[n] - q * n\n",
    "            elif nums[-1] <= q:\n",
    "                return  q * n - presum[n]\n",
    "            # 找第一个>=q的值\n",
    "            l, r = 0, n-1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if nums[mid] >= q:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            \n",
    "            return q * l - presum[l] + presum[n] - presum[l] - (n-l) * q\n",
    "        \n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(get(q))\n",
    "        \n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        presum = [0] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "        \n",
    "        for query in queries:\n",
    "            idx = bisect_left(nums, query)\n",
    "            temp = 0\n",
    "            temp += presum[-1] - presum[idx] - (len(presum) - idx - 1) * query\n",
    "            temp += idx * query - presum[idx]\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        pre_sum = list(accumulate(nums))\n",
    "        ans = []\n",
    "        for x in queries:\n",
    "            i = bisect_left(nums, x) - 1\n",
    "            cost = 0\n",
    "            right = pre_sum[-1]\n",
    "            cnt = n\n",
    "            if i >= 0:\n",
    "                cost += x * (i + 1) - pre_sum[i]\n",
    "                right -= pre_sum[i]\n",
    "                cnt -= i + 1\n",
    "            cost += right - x * cnt\n",
    "            ans.append(cost)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    You are given an array nums consisting of positive integers.\n",
    "\n",
    "    You are also given an integer array queries of size m. For the ith query, you want to make all of the elements of nums equal to queries[i]. You can perform the following operation on the array any number of times:\n",
    "\n",
    "    Increase or decrease an element of the array by 1.\n",
    "    Return an array answer of size m where answer[i] is the minimum number of operations to make all elements of nums equal to queries[i].\n",
    "\n",
    "    Note that after each query the array is reset to its original state.\n",
    "\n",
    "     \n",
    "\n",
    "    Example 1:\n",
    "\n",
    "    Input: nums = [3,1,6,8], queries = [1,5]\n",
    "    Output: [14,10]\n",
    "    Explanation: For the first query we can do the following operations:\n",
    "    - Decrease nums[0] 2 times, so that nums = [1,1,6,8].\n",
    "    - Decrease nums[2] 5 times, so that nums = [1,1,1,8].\n",
    "    - Decrease nums[3] 7 times, so that nums = [1,1,1,1].\n",
    "    So the total number of operations for the first query is 2 + 5 + 7 = 14.\n",
    "    For the second query we can do the following operations:\n",
    "    - Increase nums[0] 2 times, so that nums = [5,1,6,8].\n",
    "    - Increase nums[1] 4 times, so that nums = [5,5,6,8].\n",
    "    - Decrease nums[2] 1 time, so that nums = [5,5,5,8].\n",
    "    - Decrease nums[3] 3 times, so that nums = [5,5,5,5].\n",
    "    So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.\n",
    "    Example 2:\n",
    "\n",
    "    Input: nums = [2,9,6,3], queries = [10]\n",
    "    Output: [20]\n",
    "    Explanation: We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.\n",
    "    '''\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        # write code here\n",
    "        nums.sort()\n",
    "        prefix_sum = [0]\n",
    "\n",
    "        for num in nums:\n",
    "            prefix_sum.append(prefix_sum[-1] + num)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for query in queries:\n",
    "            left_index = bisect.bisect_left(nums, query)\n",
    "            right_index = bisect.bisect_right(nums, query)\n",
    "\n",
    "            left_sum = prefix_sum[left_index]\n",
    "            right_sum = prefix_sum[-1] - prefix_sum[right_index]\n",
    "\n",
    "            left_count = left_index\n",
    "            right_count = len(nums) - right_index\n",
    "\n",
    "            total_operations = abs(left_sum - left_count * query) + abs(right_sum - right_count * query)\n",
    "            answer.append(total_operations)\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        prefix = list(accumulate(nums, initial=0))\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        for i, x in enumerate(queries):\n",
    "            idx = bisect_left(nums, x)\n",
    "\n",
    "            res[i] = (\n",
    "                x * idx - prefix[idx] + \n",
    "                prefix[-1] - prefix[idx] - n * x + idx * x\n",
    "            )\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        s = list(accumulate(nums,initial = 0 ))\n",
    "        n =len(nums)\n",
    "        for q in queries:\n",
    "            j = bisect_left(nums,q)\n",
    "            left = s[j] -  q * j\n",
    "            right = s[n] - s[j] - q * (n-j)\n",
    "            ans.append(abs(left) + abs(right))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        s=list(accumulate(nums,initial=0))\n",
    "        res=[]\n",
    "        for q in queries:\n",
    "            c=bisect_left(nums,q)\n",
    "            left=q*c-s[c]\n",
    "            right=s[-1]-s[c]-q*(n-c)\n",
    "            res.append(left+right)\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        presum = list(accumulate(nums, initial=0))\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_left(nums, q)\n",
    "            left = q*j - presum[j]\n",
    "            right = presum[n]-presum[j] - q*(n-j)\n",
    "            ans.append(left+right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        s = list(accumulate(nums, initial=0))  # 前缀和\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_left(nums, q)\n",
    "            left = q * j - s[j]  # 蓝色面积\n",
    "            right = s[n] - s[j] - q * (n - j)  # 绿色面积\n",
    "            ans.append(left + right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        s = list(accumulate(nums, initial=0))  # 前缀和\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_left(nums, q)\n",
    "            left = q * j - s[j]  # 蓝色面积\n",
    "            right = s[n] - s[j] - q * (n - j)  # 绿色面积\n",
    "            ans.append(left + right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        s = list(accumulate(nums, initial=0))  # 前缀和\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_left(nums, q)\n",
    "            left = q * j - s[j]  # 蓝色面积\n",
    "            right = s[n] - s[j] - q * (n - j)  # 绿色面积\n",
    "            ans.append(left + right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        pre_sum = self.prefixSum(nums)\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            loc = self.binary_search(nums, query)\n",
    "            l = query * loc - pre_sum[loc]\n",
    "            r = pre_sum[-1] - pre_sum[loc] - query * (len(nums) - loc)\n",
    "            ans.append(l+r)\n",
    "        return ans    \n",
    "        \n",
    "    def binary_search(self, nums: List[int], query: int) -> int:\n",
    "        l, r = 0, len(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if nums[mid] > query:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "    \n",
    "    def prefixSum(self, nums: List[int]) -> List[int]:\n",
    "        res = [0] * (len(nums) + 1)\n",
    "        for i in range(1, len(res)):\n",
    "            res[i] = res[i-1]+nums[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        # 排序+二分+前缀和 内置函数 标准二分\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        s = list(itertools.accumulate(nums, initial=0))  # 前缀和\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            j = bisect.bisect_left(nums,q)\n",
    "            left = q * j - s[j]\n",
    "            right = s[n] - s[j] - q * (n -j)\n",
    "            res.append(left+right)\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        # TLE -> BUG\n",
    "        nums.sort()\n",
    "        npf = [nums[0]]\n",
    "        for i in nums[1:]:\n",
    "            npf.append(npf[-1]+i)\n",
    "        print(nums, npf)\n",
    "        q, n = len(queries), len(nums) \n",
    "        res = [0] * q\n",
    "        for x in range(q):  # 二分BUG\n",
    "            i, j = 0, n-1\n",
    "            t = queries[x]\n",
    "            while i < j:\n",
    "                m = (i+j)//2\n",
    "                if nums[m] <= t:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j -= 1\n",
    "            \n",
    "            left = t * i - npf[i-1]\n",
    "            right = npf[-1] - npf[i-1] - t * (n-i)\n",
    "            print(t, i, left)\n",
    "            print(t, i, right)\n",
    "\n",
    "            #print(t, i, t*(i+1)-npf[i], npf[-1]-npf[i]-t*(n-i-1))\n",
    "            res[x] =  left + right\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        li = list(accumulate(nums, operator.add, initial=0))\n",
    "        n = len(nums)\n",
    "        \n",
    "        # print(\"nums\",nums)\n",
    "        # print(\"li\",li)\n",
    "\n",
    "        def check(target: int) -> int:\n",
    "            left = bisect_left(nums, target)\n",
    "            if left == n: return n * target - li[-1]\n",
    "            # print(\"target\",target,\"left\",left)\n",
    "            leftSum = left * target - li[left]\n",
    "            # print(\"leftSum\",leftSum)\n",
    "            rightSum = li[-1] - li[left] - (n - left) * target\n",
    "            # print(\"rightSum\",rightSum)\n",
    "\n",
    "            return leftSum + rightSum\n",
    "\n",
    "\n",
    "\n",
    "        return [check(querie) for querie in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        #[1,3,6,8]\n",
    "        #[0,1,4,10,18]\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        s=list(accumulate(nums,initial=0))\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            j=bisect_left(nums,q)\n",
    "            left=j*(q)-s[j]\n",
    "            right=s[n]-s[j]-(n-j)*(q)\n",
    "            ans.append(left+right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        def lower_bound(ls, x):\n",
    "            left, right = -1, len(ls)\n",
    "            while left+1<right:\n",
    "                mid = (left+right)//2\n",
    "                if ls[mid]>=x:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            return right\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + nums[i]\n",
    "        ans = []\n",
    "        for x in queries:\n",
    "            t = 0\n",
    "            index = lower_bound(nums, x)\n",
    "            t += (x*index - pre[index])\n",
    "            t += (pre[-1]-pre[index] - x*(n-index))\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        s = list(accumulate(nums,initial = 0))\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            j = bisect_left(nums,q)\n",
    "            left = q*j - s[j]\n",
    "            right = s[n] - s[j] - (n-j)*(q)\n",
    "            ans.append(left+right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        prefix = list(accumulate(nums))\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            i = bisect_right(nums, q)\n",
    "            smaller = i * q - prefix[i - 1] if i > 0 else 0\n",
    "            bigger = prefix[-1] - (prefix[i - 1] if i > 0 else 0) - (len(nums) - i) * q\n",
    "            ans.append(smaller + bigger)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        def lower_bound(ls, x):\n",
    "            left, right = -1, len(ls)\n",
    "            while left+1<right:\n",
    "                mid = (left+right)//2\n",
    "                if ls[mid]>=x:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            return right\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + nums[i]\n",
    "        ans = []\n",
    "        for x in queries:\n",
    "            t = 0\n",
    "            index = lower_bound(nums, x)\n",
    "            t += (x*index - pre[index])\n",
    "            t += (pre[-1]-pre[index] - x*(n-index))\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n,m=len(nums),len(queries)\n",
    "        nums.sort()\n",
    "        pre_s=[0]*(n+1)\n",
    "        for i,x in enumerate(nums):\n",
    "            pre_s[i+1]=pre_s[i]+x\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            i=bisect_left(nums,q)\n",
    "            print(i)\n",
    "            left=q*i-pre_s[i]\n",
    "            right=pre_s[-1]-pre_s[i]-q*(n-i)\n",
    "            \n",
    "            ans.append(left+right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        acc=[0]\n",
    "        for i,num in enumerate(nums):\n",
    "            acc.append(acc[i]+num)\n",
    "        res=[]\n",
    "        for q in queries:\n",
    "            tmp=bisect_left(nums,q)\n",
    "            left=q*tmp-(acc[tmp]-acc[0])\n",
    "            right=acc[-1]-acc[tmp]-q*(n-tmp)\n",
    "            print(left,right)\n",
    "            res.append(left+right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minOperations(self, nums, queries) :\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        s=nums[:]\n",
    "        for i in range(1,n):\n",
    "            s[i]+=s[i-1]\n",
    "        # print(s)\n",
    "\n",
    "        res=[]\n",
    "        for i,v in enumerate(queries):\n",
    "            left,right=0,n-1\n",
    "\n",
    "            # 二分找到最后一个小于等于v的数\n",
    "            while left<=right:\n",
    "                mid=left+(right-left)//2\n",
    "                if nums[mid]<=v:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "\n",
    "            # 当所有数都大于v时，right=-1，反之为n-1\n",
    "            a,b=right,right+1\n",
    "            cur=0\n",
    "            if a!=-1:\n",
    "                cur+=(a+1)*v-s[a]\n",
    "            if b!=n:\n",
    "                if a!=-1:\n",
    "                    cur+=s[n-1]-s[a]-(n-a-1)*v\n",
    "                else:\n",
    "                    cur+=s[n-1]-n*v\n",
    "            res.append(cur)\n",
    "            # print(i,right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums_sum, n = sum(nums), len(nums)\n",
    "        nums.sort()\n",
    "        temp = []\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            temp.append(s)\n",
    "        ans = []\n",
    "        def find_num(q):\n",
    "            high, low = n-1, 0\n",
    "            while high >= low:\n",
    "                mid = low + (high-low)//2\n",
    "                if nums[mid] > q:\n",
    "                    high = mid -1\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "            return low\n",
    "        print(temp, n)\n",
    "        for q in queries:\n",
    "            index = find_num(q)\n",
    "            if index == 0:\n",
    "                path = nums_sum-n*q\n",
    "            elif index == n:\n",
    "                path = n*q - nums_sum\n",
    "            else:\n",
    "                print(index, (index*q-temp[index-1]), (nums_sum-(n-index)*q-temp[index-1]))\n",
    "                path = (index*q-temp[index-1]) + (nums_sum-(n-index)*q-temp[index-1])\n",
    "            ans.append(path)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums_sum, n = sum(nums), len(nums)\n",
    "        nums.sort()\n",
    "        temp = []\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            temp.append(s)\n",
    "        ans = []\n",
    "        def find_num(q):\n",
    "            high, low = n-1, 0\n",
    "            while high >= low:\n",
    "                mid = low + (high-low)//2\n",
    "                if nums[mid] > q:\n",
    "                    high = mid -1\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "            return low\n",
    "        print(temp, n)\n",
    "        for q in queries:\n",
    "            index = find_num(q)\n",
    "            if index == 0:\n",
    "                path = nums_sum-n*q\n",
    "            elif index == n:\n",
    "                path = n*q - nums_sum\n",
    "            else:\n",
    "                print(index, (index*q-temp[index-1]), (nums_sum-(n-index)*q-temp[index-1]))\n",
    "                path = (index*q-temp[index-1]) + (nums_sum-(n-index)*q-temp[index-1])\n",
    "            ans.append(path)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = [0]\n",
    "        for x in nums:\n",
    "            s.append(s[-1] + x)\n",
    "\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            i = bisect_right(nums, q)\n",
    "            res.append((i * q - s[i]) + (s[-1] - s[i] - q * (n - i)))\n",
    "        return res\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums_sum, n = sum(nums), len(nums)\n",
    "        nums.sort()\n",
    "        temp = []\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            temp.append(s)\n",
    "        ans = []\n",
    "        def find_num(q):\n",
    "            high, low = n-1, 0\n",
    "            while high >= low:\n",
    "                mid = low + (high-low)//2\n",
    "                if nums[mid] > q:\n",
    "                    high = mid -1\n",
    "                else:\n",
    "                    low = mid + 1\n",
    "            return low\n",
    "        print(temp, n)\n",
    "        for q in queries:\n",
    "            index = find_num(q)\n",
    "            if index == 0:\n",
    "                path = nums_sum-n*q\n",
    "            elif index == n:\n",
    "                path = n*q - nums_sum\n",
    "            else:\n",
    "                print(index, (index*q-temp[index-1]), (nums_sum-(n-index)*q-temp[index-1]))\n",
    "                path = (index*q-temp[index-1]) + (nums_sum-(n-index)*q-temp[index-1])\n",
    "            ans.append(path)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n, qlen = len(nums),len(queries)\n",
    "        nums.sort()\n",
    "        total = sum(nums)\n",
    "        pre = list(accumulate(nums,initial=0))\n",
    "        ans = [0]*qlen\n",
    "        for i,q in enumerate(queries):\n",
    "            if q<=nums[0]:\n",
    "                ans[i] = (total - q*n)\n",
    "            elif q>=nums[-1]:\n",
    "                ans[i] = (q*n - total)\n",
    "            else:\n",
    "                idx = bisect_left(nums, q)\n",
    "                ans[i] += (idx*q - (pre[idx] - pre[0]))\n",
    "                ans[i] += (pre[n]-pre[idx] - (n-idx)*q)\n",
    "            pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        # 将nums排序，二分找到查询的值q，那么在q之前的，都是增大，之后的都是减小\n",
    "        # 计算差值即可\n",
    "        n, qlen = len(nums),len(queries)\n",
    "        nums.sort()\n",
    "        total = sum(nums)\n",
    "        pre = list(accumulate(nums,initial=0))\n",
    "        ans = [0]*qlen\n",
    "        for i,q in enumerate(queries):\n",
    "            if q<=nums[0]:\n",
    "                ans[i] = (total - q*n)\n",
    "            elif q>=nums[-1]:\n",
    "                ans[i] = (q*n - total)\n",
    "            else:\n",
    "                idx = bisect_left(nums, q)\n",
    "                ans[i] += (idx*q - (pre[idx] - pre[0]))\n",
    "                ans[i] += (pre[n]-pre[idx] - (n-idx)*q)\n",
    "            pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        nums.sort()\n",
    "        x = list(accumulate(nums, initial=0))\n",
    "        res = [0] * m\n",
    "        for i,q in enumerate(queries):\n",
    "            p = bisect_left(nums, q)\n",
    "            res[i] = (p*q - x[p]) + (x[n]-x[p] - (n-p)*q)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        total = list(accumulate(nums))\n",
    "        total_div = list(accumulate(nums[::-1]))\n",
    "        # total_div = [0] + total_div\n",
    "        # total = [0] + total\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(len(queries)):\n",
    "            if queries[i] <= nums[0]:\n",
    "                ans.append(-queries[i] * n + total[-1])\n",
    "                continue\n",
    "            if queries[i] >= nums[-1]:\n",
    "                ans.append(queries[i] * n - total[-1])\n",
    "                continue\n",
    "            t = bisect_left(nums, queries[i])\n",
    "            # print(total, total_div, t)\n",
    "            ans.append((t) * queries[i] - total[t - 1] + total_div[n - t - 1] - (n - t) * queries[i])\n",
    "        return  ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        pre_sum = list(accumulate(nums, initial = 0))\n",
    "        print(pre_sum)\n",
    "        for qur in queries:\n",
    "            l, r = 0, n\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if nums[mid] < qur:l = mid + 1\n",
    "                else:r = mid\n",
    "            left = qur * l - pre_sum[l] \n",
    "            right = pre_sum[n] - pre_sum[l] - qur * (n - l)\n",
    "            ans.append(left + right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        c, ans = [0], []\n",
    "        for i in range(0, len(nums)):\n",
    "            c.append(nums[i] + c[i])\n",
    "        for query in queries:\n",
    "            bound = bisect_left(nums, query)\n",
    "            val_add = query * (bound) - c[bound]\n",
    "            val_sub = c[-1] - c[bound] - query * (len(nums)-bound)\n",
    "            ans.append(val_add+val_sub)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "        # O(n2) EXT\n",
    "        # res = []\n",
    "        # for query in queries:\n",
    "        #     res.append(sum(abs(num-query) for num in nums))\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        temp=0\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        suf=[0]+[0]*n\n",
    "        for i in range(n):\n",
    "            suf[i+1]=suf[i]+nums[i]\n",
    "        for q in queries:\n",
    "            idx=bisect.bisect_left(nums, q)\n",
    "            temp=abs(suf[idx]-idx*q)\n",
    "            print(temp)\n",
    "            temp+=abs(suf[n]-suf[idx]-(n-idx)*q)\n",
    "            print(temp)\n",
    "            ans.append(temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        accum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            accum[i + 1] = accum[i] + nums[i]\n",
    "        m = len(queries)\n",
    "        idx = sorted(list(range(m)), key=lambda x: queries[x])\n",
    "        ans = [0] * m\n",
    "        j = 0\n",
    "        for i in idx:\n",
    "            v = queries[i]\n",
    "            while j < n and nums[j] < v:\n",
    "                j += 1\n",
    "            ans[i] = j * v - accum[j] + (accum[-1] - accum[j] - (n - j) * v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        acc = list(itertools.accumulate(nums,initial=0))\n",
    "        for q in queries:\n",
    "            index = bisect.bisect_left(nums, q)\n",
    "            print(index)\n",
    "            left = index*q - acc[index]\n",
    "            right = acc[len(nums)]-acc[index]-q*(len(nums)-index)\n",
    "            res = left+right\n",
    "            ans.append(res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        prefix = [0]\n",
    "        for x in nums:\n",
    "            prefix.append(prefix[-1] + x)\n",
    "        suffix = [0]\n",
    "        for x in reversed(nums):\n",
    "            suffix.append(suffix[-1] + x)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            index = bisect.bisect_left(nums,q)\n",
    "            if index < n and nums[index] == q:\n",
    "                right = n - index - 1\n",
    "            else:\n",
    "                right = n - index\n",
    "            left = index\n",
    "            ans.append(left*q - prefix[left] + suffix[right] - right*q)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        qs = sorted(list(set(queries)))\n",
    "        n = len(nums)\n",
    "        ans = Counter()\n",
    "        pre = 0\n",
    "        idx = 0\n",
    "        nums.sort()\n",
    "        pq = qs[0]\n",
    "        for i, q in enumerate(qs):\n",
    "            cur = pre + idx * (q - pq)\n",
    "            while idx < n and nums[idx] <= q:\n",
    "                cur += q - nums[idx]\n",
    "                idx += 1\n",
    "            ans[q] += cur\n",
    "            pre = cur\n",
    "            pq = q\n",
    "        \n",
    "        pre = 0\n",
    "        idx = 0\n",
    "        pq = qs[-1]\n",
    "        nums = nums[::-1]\n",
    "        for i, q in enumerate(qs[::-1]):\n",
    "            cur = pre + idx * (pq - q)\n",
    "            while idx < n and nums[idx] >= q:\n",
    "                cur += nums[idx] - q\n",
    "                idx += 1\n",
    "            ans[q] += cur\n",
    "            pre = cur\n",
    "            pq = q\n",
    "        return [ans[q] for q in queries]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        dp=[0]*n\n",
    "        dp[0]=nums[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i]=nums[i]+dp[i-1]\n",
    "        ans=[]\n",
    "        print(dp)\n",
    "        print(nums)\n",
    "        for q in queries:\n",
    "            l=bisect.bisect_left(nums, q)\n",
    "           # print(l)\n",
    "            if l==n:\n",
    "                ans.append(q*l-dp[-1])\n",
    "            elif l==0:\n",
    "                ans.append(dp[-1]-q*n)\n",
    "            else:\n",
    "                left=(l)*q-dp[l-1]\n",
    "                right=dp[-1]-dp[l-1]-q*(n-l)\n",
    "                print(left,right,l)\n",
    "                ans.append(left+right)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        preSum = [nums[0]] * n\n",
    "        postSum = [nums[-1]] * n\n",
    "        for i in range(1, n):\n",
    "            preSum[i] = nums[i] + preSum[i-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            postSum[i] = nums[i] + postSum[i+1]\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            l, r = -1, n\n",
    "            while l + 1 != r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if nums[mid] <= q:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == -1:\n",
    "                cur = postSum[0] - n * q\n",
    "            elif r == n:\n",
    "                cur = n * q - preSum[-1]\n",
    "            else:\n",
    "                cur = (l + 1) * q - preSum[l] + postSum[l+1] - (n - 1 - l) * q\n",
    "            res.append(cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums=sorted(nums)\n",
    "        index=[i for i in range(len(queries))]\n",
    "        \n",
    "        queries=sorted([[i,j] for i,j in zip(queries,index)],key=lambda x:x[0])\n",
    "        queries,index=[i[0] for i in queries],[i[1] for i in queries]\n",
    "        L=len(nums)\n",
    "        \n",
    "        p=0\n",
    "        res=[0]\n",
    "        for i in range(L):\n",
    "            if queries[0]>nums[i]:\n",
    "                p=i\n",
    "                break\n",
    "        for i in range(L):\n",
    "            res[0]=res[0]+abs(nums[i]-queries[0])\n",
    "            \n",
    "        for i in range(1,len(queries)):\n",
    "            c=queries[i]-queries[i-1]\n",
    "            curres=res[-1]+c*p\n",
    "            newp=p\n",
    "            while newp<L and nums[newp]<=queries[i]:\n",
    "                curres=curres-abs(nums[newp]-queries[i-1])+abs(nums[newp]-queries[i])\n",
    "                newp=newp+1\n",
    "                \n",
    "            curres=curres-c*(L-newp)\n",
    "            res.append(curres)\n",
    "            p=newp\n",
    "            \n",
    "        newres=[0]*len(index)\n",
    "        for i,id in enumerate(index):\n",
    "            newres[id]=res[i]\n",
    "        return newres\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n,m=len(nums),len(queries)\n",
    "        nums.sort()\n",
    "        s=sum(nums)\n",
    "        temp=[(queries[i],i) for i in range(m)]\n",
    "        temp.sort()\n",
    "\n",
    "        res=[0]*m\n",
    "        cnt,j=0,0\n",
    "        for x,i in temp:\n",
    "            while j<n and nums[j]<=x:\n",
    "                cnt+=nums[j]\n",
    "                j+=1\n",
    "            res[i]=x*j-cnt+s-cnt-x*(n-j)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n, m = len(nums), len(queries)\n",
    "        q = sorted(zip(queries, range(m)))\n",
    "        nums.sort()\n",
    "        ans = [0] * m\n",
    "        s = sum(nums)\n",
    "        p = i = 0\n",
    "        for j, (x, idx) in enumerate(q):\n",
    "            while i < n and nums[i] <= x:\n",
    "                p += nums[i]\n",
    "                i += 1\n",
    "            ans[idx] = i * x - p + s - p - (n - i) * x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        answer=[]\n",
    "        nums=sorted(nums)\n",
    "        pre=[]\n",
    "        post=[]\n",
    "        for i, num in enumerate(nums):\n",
    "            if i==0:\n",
    "                pre.append(num)\n",
    "                post.append(sum(nums)-num)\n",
    "            else:\n",
    "                pre.append(pre[i-1]+num)\n",
    "                post.append(post[i-1]-num)\n",
    "        for query in queries:\n",
    "            number=0\n",
    "            pos=bisect.bisect_right(nums,query)\n",
    "            if pos==0:\n",
    "                number+=abs(len(nums)*query-sum(nums))\n",
    "            elif pos!=0:\n",
    "                number+=abs(pos*query-pre[pos-1])\n",
    "                number+=abs((len(nums)-pos)*query-post[pos-1])\n",
    "            answer.append(number)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        # maxNum = max(nums)\n",
    "        # minNum = min(nums)\n",
    "        # n = len(nums)\n",
    "        # res = []\n",
    "        # resDic = {}\n",
    "        # resDic[maxNum] = maxNum * n - sum(nums)\n",
    "        # resDic[minNum] = sum(nums) - minNum * n\n",
    "        # for i in range(len(queries)):\n",
    "        #     if queries[i] in resDic:\n",
    "        #         res.append(resDic[queries[i]])\n",
    "        #     else:\n",
    "        #         if queries[i] > maxNum:\n",
    "        #             numActs = resDic[maxNum] + (queries[i] - maxNum) * n\n",
    "        #             res.append(numActs)\n",
    "        #             resDic[queries[i]] = numActs\n",
    "        #         elif queries[i] < minNum:\n",
    "        #             numActs = resDic[minNum] + (minNum - queries[i]) * n\n",
    "        #             res.append(numActs)\n",
    "        #             resDic[queries[i]] = numActs\n",
    "        #         else:\n",
    "        #             numActs = 0\n",
    "        #             for num in nums:\n",
    "        #                 numActs += abs(num - queries[i])\n",
    "        #             res.append(numActs)\n",
    "        #             resDic[queries[i]] = numActs\n",
    "        # return res\n",
    "        maxNum = max(nums)\n",
    "        minNum = min(nums)\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        resDic = {}\n",
    "        resDic[maxNum] = maxNum * n - sum(nums)\n",
    "        resDic[minNum] = sum(nums) - minNum * n\n",
    "        qsort = queries.copy()\n",
    "        qsort = list(set(qsort))\n",
    "        qsort.sort()\n",
    "        nums.sort()\n",
    "        ni = -1\n",
    "        nj = -1\n",
    "        # ni + 1 <= qi, n - ni - 1 > qi\n",
    "        # nj + 1 <= qj, n - nj - 1 > qj\n",
    "        # qi < ni + 1 ~ nj < qj\n",
    "        qbefore = 0\n",
    "        for q in qsort:\n",
    "            if q > minNum and q < maxNum:\n",
    "                if ni < 0:\n",
    "                    ni = 0\n",
    "                    numActs = 0\n",
    "                    while nums[ni] <= q:\n",
    "                        numActs += q - nums[ni]\n",
    "                        ni += 1\n",
    "                    for i in range(ni, n):\n",
    "                        numActs += nums[i] - q\n",
    "                    resDic[q] = numActs  \n",
    "                    qbefore = q\n",
    "                else:\n",
    "                    nj = ni\n",
    "                    numActs = resDic[qbefore]\n",
    "                    while nums[nj] <= q:\n",
    "                        numActs = numActs - (nums[nj] - qbefore) + (q - nums[nj])\n",
    "                        nj += 1\n",
    "                    numActs = numActs - (q - qbefore) * (n - nj) + (q - qbefore) * (ni)\n",
    "                    resDic[q] = numActs\n",
    "                    qbefore = q\n",
    "                    ni = nj\n",
    "            elif q <= minNum:\n",
    "                resDic[q] = resDic[minNum] + (minNum - q) * n\n",
    "            else:\n",
    "                resDic[q] = resDic[maxNum] + (q - maxNum) * n\n",
    "        for qq in queries:\n",
    "            res.append(resDic[qq])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        sm = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            sm.append(sm[i-1] + nums[i])\n",
    "        # print(nums)\n",
    "        # print(sm)\n",
    "        dc = {}\n",
    "        def func(x):\n",
    "            if dc.get(x) is not None:\n",
    "                return dc[x]\n",
    "            pos = bisect.bisect_left(nums, x)\n",
    "            # print(x, pos)\n",
    "            if not pos:\n",
    "                sleft, sright = 0, sm[-1]\n",
    "            else:\n",
    "                sleft, sright = sm[pos - 1], sm[-1] - sm[pos - 1]\n",
    "            dc[x] = x * pos - sleft + sright - x * (len(nums) - pos)\n",
    "            return dc[x]\n",
    "        return [func(q) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        presum = [0]\n",
    "        for num in nums:\n",
    "            presum.append(num+presum[-1])\n",
    "        res = []\n",
    "        seen = dict()\n",
    "        n = len(nums)\n",
    "        seen[1] = sum(nums)-n\n",
    "        for query in queries:\n",
    "            if query in seen:\n",
    "                res.append(seen[query])\n",
    "            else:\n",
    "                idx = bisect.bisect_left(nums,query)\n",
    "                s = (idx*query-presum[idx]) + (presum[-1]-presum[idx])-(n-idx)*query\n",
    "                seen[query] = s\n",
    "                res.append(s)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: List[int], q: List[int]) -> List[int]:\n",
    "        res = [0] * len(q)\n",
    "        n.sort()\n",
    "        a1 = [0] * len(n)\n",
    "        a2 = [0] * len(n)\n",
    "        a1[0] = n[0]\n",
    "        a2[0] = sum(n)\n",
    "        for i in range(1, len(n)):\n",
    "            a1[i] = n[i] + a1[i - 1]\n",
    "            a2[i] = a2[i - 1] - n[i - 1]\n",
    "        a1 = [0] + a1\n",
    "        a2 = a2 + [0]\n",
    "        for i in range(len(q)):\n",
    "            s = 0\n",
    "            l, r = 0, len(n) - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if n[mid] < q[i]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            s += (q[i] * l - a1[l]) + (a2[l] - (q[i] * (len(n) - l)))\n",
    "            res[i] = s\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        q = []\n",
    "        for i, x in enumerate(queries):\n",
    "            q.append((x, i))\n",
    "        q.sort()\n",
    "        nums.sort()\n",
    "        cnt, ans = 0, [0] * len(q)\n",
    "        j = -1\n",
    "        for i, x in enumerate(nums):\n",
    "            cnt += abs(q[0][0] - x)\n",
    "            if q[0][0] >= x: \n",
    "                j = i\n",
    "        ans[q[0][1]] = cnt\n",
    "        pre = q[0][0]\n",
    "        for i in range(1, len(q)):\n",
    "            x, idx = q[i]\n",
    "            pos, neg = 0, 0\n",
    "            k = j + 1\n",
    "            while k < len(nums) and x >= nums[k]:\n",
    "                pos += abs(pre - nums[k])\n",
    "                neg += x - nums[k]\n",
    "                k += 1\n",
    "          \n",
    "            cnt = cnt + (j + 1) * (x - pre) - (len(nums) - k) * (x - pre) + neg - pos\n",
    "            ans[idx] = cnt\n",
    "            j = k - 1\n",
    "            pre = x\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:\n",
    "        n,m=len(nums),len(queries)\n",
    "        nums.sort();queries=sorted([(queries[i],i) for i in range(m)])\n",
    "        f,sumf,l=0,sum(nums),0\n",
    "        for i in range(m):\n",
    "            while(l<n and nums[l]<queries[i][0]):f+=nums[l];l+=1\n",
    "            queries[i]=(queries[i][1],queries[i][0]*l-f+sumf-f-queries[i][0]*(n-l))\n",
    "        queries.sort()\n",
    "        return [i[1] for i in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        #copy\n",
    "        ans = sum = 0\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k:\n",
    "                    return -1\n",
    "                sum += x//k\n",
    "                if x>0 :\n",
    "                    ans += x//k\n",
    "            elif x:\n",
    "                return -1\n",
    "        return -1 if sum else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        res = _sum = 0\n",
    "        for i in range(len(nums1)):\n",
    "            diff = nums1[i] - nums2[i]\n",
    "            \n",
    "            if k:\n",
    "                if diff % k:\n",
    "                    return -1\n",
    "                _sum += diff // k\n",
    "                if diff > 0:\n",
    "                    res += diff // k\n",
    "            else:\n",
    "                if diff:\n",
    "                    return -1\n",
    "        return -1 if _sum else res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n=len(nums1)\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            return -1\n",
    "        s=0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x=(nums1[i]-nums2[i])\n",
    "            if x%k!=0:\n",
    "                return -1\n",
    "            if x>0:\n",
    "                s+=x//k\n",
    "            elif x<0:\n",
    "                ans+=x//k\n",
    "        if s+ans!=0:\n",
    "            return -1\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            if nums1 == nums2:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        res = 0\n",
    "        flag = 0\n",
    "        for i in range(len(nums1)):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                continue\n",
    "            if abs(nums1[i] - nums2[i]) % k != 0:\n",
    "                return -1\n",
    "            elif nums1[i] > nums2[i]:\n",
    "                flag += (nums1[i] - nums2[i]) / k\n",
    "            else:\n",
    "                flag -= (nums2[i] - nums1[i]) / k\n",
    "                res += (nums2[i] - nums1[i]) / k\n",
    "\n",
    "        if flag != 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        #copy\n",
    "        ans = sum = 0\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k:\n",
    "                    return -1\n",
    "                sum += x//k\n",
    "                if x>0 :\n",
    "                    ans += x//k\n",
    "            elif x:\n",
    "                return -1\n",
    "        return -1 if sum else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        sum_list = 0\n",
    "        ans = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y \n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum_list += x // k\n",
    "                if x > 0: ans += x // k\n",
    "            elif x: return -1\n",
    "        return -1 if sum_list else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        ans = sum = 0\n",
    "\n",
    "        for x, y in zip(nums1, nums2):\n",
    "\n",
    "            x -= y\n",
    "\n",
    "            if k:\n",
    "\n",
    "                if x % k: return -1\n",
    "\n",
    "                sum += x // k\n",
    "\n",
    "                if x > 0: ans += x // k\n",
    "\n",
    "            elif x: return -1\n",
    "\n",
    "        return -1 if sum else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        xiao=0\n",
    "        da=0\n",
    "        for i in range(len(nums1)):\n",
    "            cha=nums1[i]-nums2[i]\n",
    "            if(cha<0):\n",
    "                if(k==0):\n",
    "                    return -1\n",
    "                else:\n",
    "                    if((-cha)%k!=0):\n",
    "                        return -1\n",
    "                    else:\n",
    "                        xiao=xiao+int((-cha)/k)\n",
    "            if(cha>0):\n",
    "                if(k==0):\n",
    "                    return -1\n",
    "                else:\n",
    "                    if(cha%k!=0):\n",
    "                        return -1\n",
    "                    else:\n",
    "                        da=da+int(cha/k)\n",
    "        if(xiao==da):\n",
    "            return xiao\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n=len(nums1)\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            return -1\n",
    "        s=0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            x=(nums1[i]-nums2[i])\n",
    "            if x%k!=0:\n",
    "                return -1\n",
    "            if x>0:\n",
    "                s+=x//k\n",
    "            elif x<0:\n",
    "                ans+=x//k\n",
    "        if s+ans!=0:\n",
    "            return -1\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        less=over=0\n",
    "        for i in range(len(nums1)):\n",
    "            diff = abs(nums1[i]-nums2[i])\n",
    "            if diff%k!=0:\n",
    "                return -1\n",
    "            if nums1[i]>nums2[i]:\n",
    "                over+=diff//k\n",
    "            elif nums1[i]<nums2[i]:\n",
    "                less+=diff//k\n",
    "        \n",
    "        if over==less:\n",
    "            return over\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import operator\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if sum(nums1) != sum(nums2):\n",
    "            return -1\n",
    "        if operator.eq(nums1, nums2):\n",
    "            return 0\n",
    "        elif k == 0:\n",
    "            return -1\n",
    "        n = len(nums1)\n",
    "        bigger = 0\n",
    "        for i in range(n):\n",
    "            if nums1[i] > nums2[i]:\n",
    "                a = nums1[i] - nums2[i]\n",
    "                if a % k != 0:\n",
    "                    return -1\n",
    "                bigger += a\n",
    "            elif nums1[i] < nums2[i]:\n",
    "                if (nums2[i] - nums1[i]) % k != 0:\n",
    "                    return -1\n",
    "        return bigger // k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, a: List[int], b: List[int], k: int) -> int:\n",
    "        if sum(a)!=sum(b):\n",
    "            return -1\n",
    "        if k==0:\n",
    "            return 0 if all(i==j for i,j in zip(a,b)) else -1\n",
    "        ans=0\n",
    "        for i,j in zip(a,b):\n",
    "            if abs(i-j)%k!=0:\n",
    "                return -1\n",
    "            if i>j:\n",
    "                ans+=(i-j)//k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n=len(nums1)\n",
    "\n",
    "        ans1=0\n",
    "        ans2=0\n",
    "        if k==0:\n",
    "            for i in range(n):\n",
    "                if nums1[i]!=nums2[i]:\n",
    "                    return -1;\n",
    "            return 0\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            a=nums1[i]-nums2[i]\n",
    "            if a%k!=0: return -1\n",
    "            a=a//k\n",
    "            if a>=0:\n",
    "                ans1+=a\n",
    "            else:\n",
    "                ans2+=abs(a)\n",
    "        if ans1!=ans2:return -1\n",
    "        return ans1\n",
    "            \n",
    "\n",
    "                \n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        neg = 0\n",
    "        pos = 0\n",
    "        if k==0:\n",
    "            return 0  if all(nums1[i]==nums2[i] for i in range(len(nums1))) else -1\n",
    "        for i in range(len(nums1)):\n",
    "            diff = nums1[i] - nums2[i]\n",
    "            if (diff % k) == 0:\n",
    "                if diff > 0:\n",
    "                    pos += diff // k\n",
    "                else:\n",
    "                    neg += abs(diff // k)\n",
    "            else:\n",
    "                return -1\n",
    "        return neg if neg==pos else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            if nums1 == nums2:  return 0\n",
    "            else:   return -1\n",
    "        pos = neg = 0\n",
    "        for num1, num2 in zip(nums1, nums2):\n",
    "            if (num1 - num2) % k != 0:  return -1\n",
    "            if num1 < num2: neg += (num2 - num1) // k\n",
    "            else:   pos += (num1 - num2) // k\n",
    "        if pos == neg:  return pos\n",
    "        else:   return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k==0:\n",
    "            if nums1!=nums2:\n",
    "                return -1\n",
    "            return 0\n",
    "        n=len(nums1)\n",
    "        a,b=0,0\n",
    "        for i in range(len(nums1)):\n",
    "            if nums1[i]<nums2[i]:\n",
    "                if (nums2[i]-nums1[i])%k==0:\n",
    "                    a+=(nums2[i]-nums1[i])//k\n",
    "                else:\n",
    "                    return -1\n",
    "            elif nums1[i]>nums2[i]:\n",
    "                if (nums1[i]-nums2[i])%k==0:\n",
    "                    b+=(nums1[i]-nums2[i])//k\n",
    "                else:\n",
    "                    return -1\n",
    "        return a if a==b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            if nums1 == nums2:\n",
    "                return 0\n",
    "            return -1\n",
    "\n",
    "        n = len(nums1)\n",
    "        diff = []\n",
    "        res = 0\n",
    "        s = 0\n",
    "        for index in range(n):\n",
    "            diff = nums1[index] - nums2[index]\n",
    "            s += diff\n",
    "            if diff % k != 0:\n",
    "                return -1\n",
    "            elif diff > 0:\n",
    "                res += diff // k\n",
    "        \n",
    "        if s == 0:\n",
    "            return res\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        r1 = r2 = 0\n",
    "        ans = 0\n",
    "        if k == 0:\n",
    "            for x,y in zip(nums1,nums2) :\n",
    "                if x!=y :\n",
    "                    return -1\n",
    "            return 0\n",
    "        for x,y in zip(nums1,nums2) :\n",
    "            r1 += x\n",
    "            r2 += y\n",
    "            if abs(x-y) %k != 0 :\n",
    "                return -1\n",
    "            if x > y :\n",
    "                ans += (x-y) //k\n",
    "        return ans if r1== r2 else -1        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1,nums2):\n",
    "            x -= y\n",
    "            if k :\n",
    "                if x%k :return -1\n",
    "                sum += x//k\n",
    "                if x>0 :ans += x//k\n",
    "            elif x: return -1\n",
    "        return -1 if sum else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\r\n",
    "        n = len(nums1)\r\n",
    "\r\n",
    "        if k == 0:\r\n",
    "            for i in range(n):\r\n",
    "                if nums1[i] != nums2[i]:\r\n",
    "                    return -1\r\n",
    "            return 0\r\n",
    "\r\n",
    "        add_op = 0\r\n",
    "        sub_op = 0\r\n",
    "        for i in range(n):\r\n",
    "            if abs(nums1[i] - nums2[i]) % k:\r\n",
    "                return -1\r\n",
    "            cur_op = abs(nums1[i] - nums2[i]) // k\r\n",
    "\r\n",
    "            if nums1[i] > nums2[i]:\r\n",
    "                sub_op += cur_op\r\n",
    "            elif nums1[i] < nums2[i]:\r\n",
    "                add_op += cur_op\r\n",
    "        \r\n",
    "        if add_op == sub_op:\r\n",
    "            return add_op\r\n",
    "        else:\r\n",
    "            return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = 0  # 最少需要的操作次数\n",
    "        sum = 0  # 总共需要的操作次数\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y  # 计算差异\n",
    "            if k:\n",
    "                if x % k:  # 如果差异不能被k整除，返回-1\n",
    "                    return -1\n",
    "                sum += x // k  # 累加总共需要的操作次数\n",
    "                if x > 0:  # 只有当差异为正数时，才需要增加操作\n",
    "                    ans += x // k  \n",
    "            elif x:  # 如果k为0但差异不为0，返回-1\n",
    "                return -1\n",
    "        return -1 if sum else ans  # 如果总差异为0，返回最少需要的操作次数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return -1 if nums1 != nums2 else 0\n",
    "        # 计算相邻数之间的差值，为正或为负的数量，如果不是k的倍数，返回-1\n",
    "        pos = neg = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            cnt, rest = divmod(x - y, k)\n",
    "            if rest:\n",
    "                return -1\n",
    "            if cnt > 0:\n",
    "                pos += cnt\n",
    "            elif cnt < 0:\n",
    "                neg -= cnt\n",
    "        if pos != neg:\n",
    "            return -1\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum += x // k\n",
    "                if x > 0: ans += x // k\n",
    "            elif x: return -1\n",
    "        return -1 if sum else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n = len(nums1)\n",
    "        cnt0 = cnt1 = 0\n",
    "        if k == 0:\n",
    "            if nums1 == nums2:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        for i in range(n):\n",
    "            if abs(nums1[i] - nums2[i]) % k != 0:\n",
    "                return -1\n",
    "            if nums1[i] > nums2[i]:\n",
    "                cnt0 += (nums1[i] - nums2[i]) // k\n",
    "            else:\n",
    "                cnt1 += (nums2[i] - nums1[i]) // k\n",
    "        if cnt0 != cnt1:\n",
    "            return -1\n",
    "        return cnt0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        c1=0\n",
    "        c2=0\n",
    "        if k==0:\n",
    "            for i in range(len(nums1)):\n",
    "                if nums1[i]!=nums2[i]:\n",
    "                    return -1\n",
    "            return 0\n",
    "        for i in range(len(nums1)):\n",
    "            if nums1[i]>nums2[i]:\n",
    "                if (nums1[i]-nums2[i])%k!=0:\n",
    "                    return-1\n",
    "                c1+=(nums1[i]-nums2[i])//k\n",
    "            else:\n",
    "                if (nums2[i]-nums1[i])%k!=0:\n",
    "                    return-1\n",
    "                c2+=(nums2[i]-nums1[i])//k\n",
    "        if c1==c2:\n",
    "            return c1\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum += x // k\n",
    "                if x > 0: ans += x // k\n",
    "            elif x: return -1\n",
    "        return -1 if sum else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if sum(nums1) != sum(nums2):\n",
    "            return - 1\n",
    "        if k == 0:\n",
    "            for nu1, nu2 in zip(nums1, nums2):\n",
    "                if nu1 != nu2:\n",
    "                    return -1\n",
    "        ans = 0\n",
    "        for nu1, nu2 in zip(nums1, nums2):\n",
    "            if nu1 == nu2: continue\n",
    "            if (nu1 - nu2) % k == 0:\n",
    "                ans += abs(nu1 - nu2) // k\n",
    "            else:\n",
    "                return -1\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0 if nums1 == nums2 else -1\n",
    "        n = len(nums1)\n",
    "        add = [0, 0]\n",
    "        for i in range(n):\n",
    "            d = nums1[i] - nums2[i]\n",
    "            if d % k:\n",
    "                return -1\n",
    "            add[d < 0] += abs(d) // k\n",
    "        if add[0] != add[1]:\n",
    "            return -1\n",
    "        return add[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k:return -1\n",
    "                sum += x//k\n",
    "                if x>0:ans += x//k\n",
    "            elif x: return -1\n",
    "        return -1 if k and sum else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum += x // k\n",
    "                if x > 0: ans += x // k\n",
    "            elif x: return -1\n",
    "        return -1 if sum else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums1)\n",
    "        sum1,sum2 = sum(nums1),sum(nums2)\n",
    "        if sum1 != sum2:\n",
    "            return -1\n",
    "\n",
    "        if k == 0:\n",
    "            if all([nums1[i] == nums2[i] for i in range(n)]):\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums1[i] - nums2[i]\n",
    "            if x % k != 0:\n",
    "                return -1\n",
    "\n",
    "            if x > 0:\n",
    "                ans += x // k\n",
    "\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0 if nums1 == nums2 else -1\n",
    "        n = len(nums1)\n",
    "        pos = neg = 0\n",
    "        for i in range(n):\n",
    "            x = nums1[i]-nums2[i]\n",
    "            if x % k:\n",
    "                return -1\n",
    "            if x > 0:\n",
    "                pos += x//k\n",
    "            else:\n",
    "                neg -= x//k\n",
    "        return pos if pos == neg else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if len(nums1)!=len(nums2):\n",
    "            return -1\n",
    "        addcnt=0\n",
    "        minuscnt=0\n",
    "        for i in range(0,len(nums1)):\n",
    "            dif=nums1[i]-nums2[i]\n",
    "            if k==0:\n",
    "                if dif==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    return -1\n",
    "            if dif%k!=0:\n",
    "                return -1\n",
    "            if dif>0:\n",
    "                addcnt+=(dif//k)\n",
    "            elif dif<0:\n",
    "                minuscnt+=(-dif//k)\n",
    "        if addcnt==minuscnt:\n",
    "            return addcnt\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum += x // k\n",
    "                if x > 0: ans += x // k\n",
    "            elif x: return -1\n",
    "        return -1 if sum else ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if sum(nums1) != sum(nums2) or len(nums1) != len(nums2) or k == 0:\n",
    "            if nums1 == nums2:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "        ans = 0\n",
    "        for i in range(len(nums1)):\n",
    "            x = nums1[i] - nums2[i]\n",
    "            if x%k != 0:\n",
    "                return -1\n",
    "            if x > 0:\n",
    "                ans += x//k\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if not k: return 0 if nums1 == nums2 else -1\n",
    "        sumPos = sumNeg = res = 0\n",
    "        for n1, n2 in zip(nums1, nums2):\n",
    "            if n1 == n2: continue\n",
    "            if n1 > n2:\n",
    "                n2 -= n1\n",
    "                sumPos += n2\n",
    "                n2, r = divmod(n2, k)\n",
    "                if r: return -1\n",
    "                res -= n2\n",
    "            else:\n",
    "                n1 -= n2\n",
    "                sumNeg += n1\n",
    "                n1, r = divmod(n1, k)\n",
    "                if r: return -1\n",
    "                res -= n1\n",
    "        if sumPos != sumNeg: return -1\n",
    "        return res >> 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        a=b=0\n",
    "        if k==0:\n",
    "            return 0 if nums1==nums2 else -1  #坑\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            if x>y:\n",
    "                w=x-y\n",
    "                if w%k!=0:\n",
    "                    return -1\n",
    "                a+=w\n",
    "            else:\n",
    "                w=y-x\n",
    "                if w%k!=0:\n",
    "                    return -1\n",
    "                b+=w \n",
    "        return -1 if a!=b else b//k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k==0:\n",
    "            if nums1!=nums2:\n",
    "                return -1\n",
    "            return 0\n",
    "        n=len(nums1)\n",
    "        a,b=0,0\n",
    "        for i in range(len(nums1)):\n",
    "            if nums1[i]<nums2[i]:\n",
    "                if (nums2[i]-nums1[i])%k==0:\n",
    "                    a+=(nums2[i]-nums1[i])//k\n",
    "                else:\n",
    "                    return -1\n",
    "            elif nums1[i]>nums2[i]:\n",
    "                if (nums1[i]-nums2[i])%k==0:\n",
    "\n",
    "                    b+=(nums1[i]-nums2[i])//k\n",
    "                else:\n",
    "                    return -1\n",
    "        return a if a==b else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum += x //k\n",
    "                if x > 0 : ans += x //k\n",
    "            elif x:return -1\n",
    "        return -1 if sum else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "            i ,j    \n",
    "            nums1[i]= nums1[i]+k\n",
    "            nums1[j] =nums1[j]-k\n",
    "            使得  nums1=nums2\n",
    "            if nums1[i]==nums2[i]  则 不应该改变\n",
    "            if nums1[i]>nums2[i]  答案肯定为 -1\n",
    "        \"\"\"\n",
    "        n = len(nums1)\n",
    "        cnt = 0\n",
    "        s = 0\n",
    "        if nums1 == nums2:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1\n",
    "\n",
    "        for i,(x,y) in enumerate(zip(nums1,nums2)):\n",
    "            if x == y:\n",
    "                continue \n",
    "            elif x>y:\n",
    "                if (x-y)%k:\n",
    "                    return -1\n",
    "                cnt -=(x-y)//k\n",
    "                s += (x-y)//k\n",
    "            else:\n",
    "                if (y-x)%k:\n",
    "                    return -1\n",
    "                cnt +=(y-x)//k\n",
    "                s+=(y-x)//k\n",
    "        return -1 if cnt else s//2 \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if sum(nums1) != sum(nums2):\n",
    "            return -1\n",
    "        if k == 0:\n",
    "            if nums2 != nums1:\n",
    "                return -1\n",
    "            else:\n",
    "                return 0\n",
    "        rest = 0\n",
    "        cnt = 0\n",
    "        for i in range(len(nums1)):\n",
    "            if (nums1[i] - nums2[i]) % k != 0:\n",
    "                return -1\n",
    "            need = (nums2[i] - nums1[i]) // k  # + 给 - 收\n",
    "            if need == 0:\n",
    "                continue\n",
    "            if rest > 0 and need > 0:\n",
    "                rest = rest - need\n",
    "                cnt += abs(rest) if rest < 0 else 0\n",
    "            elif rest < 0 and need < 0:\n",
    "                rest = rest - need\n",
    "                cnt += abs(rest) if rest > 0 else 0\n",
    "            else:\n",
    "                cnt += abs(need)\n",
    "                rest = rest - need\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = sum = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            x -= y\n",
    "            if k:\n",
    "                if x % k: return -1\n",
    "                sum += x // k\n",
    "                if x > 0: ans += x // k\n",
    "            elif x: return -1\n",
    "        return -1 if sum else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        tem = 0\n",
    "        n = len(nums1)\n",
    "        if k == 0:\n",
    "            return 0 if all(nums1[i]==nums2[i] for i in range(n)) else -1\n",
    "        for i in range(n):\n",
    "            t = nums1[i]-nums2[i]\n",
    "            if t%k==0:\n",
    "                tem += t//k\n",
    "                ans += abs(t//k)\n",
    "            else:\n",
    "                return -1\n",
    "        return ans//2 if tem==0 and ans%2==0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if not k: return 0 if nums1 == nums2 else -1\n",
    "        pos, neg = [], []\n",
    "        sumPos = sumNeg = res = 0\n",
    "        for n1, n2 in zip(nums1, nums2):\n",
    "            if n1 == n2: continue\n",
    "            if n1 > n2:\n",
    "                n2 -= n1\n",
    "                sumPos += n2\n",
    "                n2, r = divmod(n2, k)\n",
    "                if r: return -1\n",
    "                res -= n2\n",
    "            else:\n",
    "                n1 -= n2\n",
    "                sumNeg += n1\n",
    "                n1, r = divmod(n1, k)\n",
    "                if r: return -1\n",
    "                res -= n1\n",
    "        if sumPos != sumNeg: return -1\n",
    "        return res >> 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            else:\n",
    "                return -1\n",
    "            \n",
    "        \n",
    "        add_c=0\n",
    "        sub_c=0\n",
    "        tmp=0\n",
    "\n",
    "        for i in range(len(nums1)):\n",
    "            tmp=nums1[i]-nums2[i]\n",
    "            if tmp%k!=0:\n",
    "                return -1\n",
    "            if tmp>0:\n",
    "                add_c+=tmp//k\n",
    "            else:\n",
    "                sub_c+=tmp//k\n",
    "        \n",
    "        if add_c+sub_c==0:\n",
    "            return add_c\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0 if nums1 == nums2 else -1\n",
    "        res, total = 0, 0\n",
    "        for i, x in enumerate(nums1):\n",
    "            d = x - nums2[i]\n",
    "            if d % k != 0:\n",
    "                return -1\n",
    "            d //= k\n",
    "            if d > 0:\n",
    "                res += d\n",
    "            total += d\n",
    "        return res if total == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if nums1 == nums2:\n",
    "            return 0\n",
    "        total_neg = 0\n",
    "        total_pos = 0\n",
    "        if k == 0:\n",
    "            return - 1\n",
    "        for i in range(0,len(nums1)):\n",
    "            if (abs(nums1[i] - nums2[i]) / k) % 1 != 0:\n",
    "                return -1\n",
    "            else:\n",
    "                print(total_neg,total_pos)\n",
    "                if nums1[i] < nums2[i]:\n",
    "                    total_pos += int((nums2[i] - nums1[i]) / k)\n",
    "                elif nums1[i] > nums2[i]:\n",
    "                    total_neg += int((nums1[i] - nums2[i]) / k)\n",
    "        if total_neg == total_pos:\n",
    "            return total_pos\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0 if nums1 == nums2 else -1\n",
    "        if nums1 == nums2:\n",
    "            return 0\n",
    "        n = len(nums1)\n",
    "        record = {1:[],2:[]}  # 记录nums1比nums2大的位置\n",
    "        for i in range(n):\n",
    "            diff = nums1[i] - nums2[i]\n",
    "            if diff % k == 0:\n",
    "                if diff > 0:\n",
    "                    record[1].append(diff // k)\n",
    "                if diff < 0 :\n",
    "                    record[2].append(-diff // k)\n",
    "            else:\n",
    "                return -1\n",
    "        print(record[1],record[2])\n",
    "        if sum(record[1]) != sum(record[2]):\n",
    "            return -1\n",
    "        return sum(record[1]) if record[1] else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        diff = [n1-n2 for n1, n2 in zip(nums1, nums2)]\n",
    "        pos, neg = 0, 0\n",
    "        if k == 0:\n",
    "            for item in diff:\n",
    "                if item != 0:\n",
    "                    return -1\n",
    "            return 0\n",
    "        \n",
    "        for num in diff:\n",
    "            if num % k != 0:\n",
    "                return -1\n",
    "            if num > 0:\n",
    "                pos += num\n",
    "            else:\n",
    "                neg += num\n",
    "        if pos + neg != 0:\n",
    "            return -1\n",
    "\n",
    "        return pos // k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        arr=[]\n",
    "        tot=[]\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(len(nums1)):\n",
    "                x=nums1[i]-nums2[i]\n",
    "                if x%k!=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    if x>0:\n",
    "                        arr.append(x//k)\n",
    "                    elif x<0:\n",
    "                        tot.append(-x//k)\n",
    "        arr.sort(reverse=True)\n",
    "        tot.sort(reverse=True)\n",
    "        p=q=0\n",
    "        ans=0\n",
    "        while p<len(arr) and q<len(tot):\n",
    "            if arr[p]>tot[q]:\n",
    "                arr[p]-=tot[q]\n",
    "                ans+=tot[q]\n",
    "                q+=1\n",
    "            elif arr[p]<tot[q]:\n",
    "                tot[q]-=arr[p]\n",
    "                ans+=arr[p]\n",
    "                p+=1\n",
    "            else:\n",
    "                \n",
    "                ans+=arr[p]\n",
    "                p+=1\n",
    "                q+=1\n",
    "        if p<len(arr) or q<len(tot):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        diff=[x-y for x,y in zip(nums1,nums2)]\n",
    "        if k==0:\n",
    "            return 0 if all(x==0 for x in diff) else -1\n",
    "        p,n=0,0\n",
    "        for d in diff:\n",
    "            if abs(d)%k!=0:return -1\n",
    "            if d>0:\n",
    "                p+=d \n",
    "            else:\n",
    "                n-=d \n",
    "        return -1 if p!=n else p//k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        q=[]\n",
    "        ans=0\n",
    "        if k==0:\n",
    "            return 0 if nums1==nums2 else -1\n",
    "        for x,y in zip(nums1,nums2):\n",
    "            if (x-y)%k!=0:\n",
    "                return -1\n",
    "            q.append(x-y)\n",
    "        q.sort()\n",
    "        l=0\n",
    "        for x in q:\n",
    "            if x<0: \n",
    "               l+=x \n",
    "       \n",
    "        if (-l)//k==(sum(q)-l)//k:\n",
    "           \n",
    "            return (-l)//k\n",
    "        else :\n",
    "            return -1\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        arr=[]\n",
    "        tot=[]\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(len(nums1)):\n",
    "                x=nums1[i]-nums2[i]\n",
    "                if x%k!=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    if x>0:\n",
    "                        arr.append(x//k)\n",
    "                    elif x<0:\n",
    "                        tot.append(-x//k)\n",
    "        arr.sort(reverse=True)\n",
    "        tot.sort(reverse=True)\n",
    "        p=q=0\n",
    "        ans=0\n",
    "        while p<len(arr) and q<len(tot):\n",
    "            if arr[p]>tot[q]:\n",
    "                arr[p]-=tot[q]\n",
    "                ans+=tot[q]\n",
    "                q+=1\n",
    "            elif arr[p]<tot[q]:\n",
    "                tot[q]-=arr[p]\n",
    "                ans+=arr[p]\n",
    "                p+=1\n",
    "            else:\n",
    "                \n",
    "                ans+=arr[p]\n",
    "                p+=1\n",
    "                q+=1\n",
    "        if p<len(arr) or q<len(tot):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0 if nums1 == nums2 else -1\n",
    "        n = len(nums1)\n",
    "        record = {1:[],2:[]}  # 记录nums1比nums2大的位置\n",
    "        for i in range(n):\n",
    "            diff = nums1[i] - nums2[i]\n",
    "            if diff % k == 0:\n",
    "                if diff > 0:\n",
    "                    record[1].append(diff // k)\n",
    "                if diff < 0 :\n",
    "                    record[2].append(-diff // k)\n",
    "            else:\n",
    "                return -1\n",
    "        print(record[1],record[2])\n",
    "        if sum(record[1]) != sum(record[2]):\n",
    "            return -1\n",
    "        if nums1 == nums2:\n",
    "            return 0\n",
    "        return sum(record[1]) if record[1] else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n=len(nums1)\n",
    "        a=[nums1[i]-nums2[i] for i in range(n)]\n",
    "        if sum(a)!=0:\n",
    "            return -1\n",
    "        ans=0\n",
    "        if k==0:\n",
    "            for x in a:\n",
    "                if x!=0:\n",
    "                    return -1\n",
    "            return 0\n",
    "        for x in a:\n",
    "            if x%k!=0:\n",
    "                return -1\n",
    "            if x>0:\n",
    "                ans+= x//k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        arr=[]\n",
    "        tot=[]\n",
    "        if k==0:\n",
    "            if nums1==nums2:\n",
    "                return 0\n",
    "            return -1\n",
    "        else:\n",
    "            for i in range(len(nums1)):\n",
    "                x=nums1[i]-nums2[i]\n",
    "                if x%k!=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    if x>0:\n",
    "                        arr.append(x//k)\n",
    "                    elif x<0:\n",
    "                        tot.append(-x//k)\n",
    "        arr.sort(reverse=True)\n",
    "        tot.sort(reverse=True)\n",
    "        p=q=0\n",
    "        ans=0\n",
    "        while p<len(arr) and q<len(tot):\n",
    "            if arr[p]>tot[q]:\n",
    "                arr[p]-=tot[q]\n",
    "                ans+=tot[q]\n",
    "                q+=1\n",
    "            elif arr[p]<tot[q]:\n",
    "                tot[q]-=arr[p]\n",
    "                ans+=arr[p]\n",
    "                p+=1\n",
    "            else:\n",
    "                \n",
    "                ans+=arr[p]\n",
    "                p+=1\n",
    "                q+=1\n",
    "        if p<len(arr) or q<len(tot):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if nums1 == nums2: return 0\n",
    "        if k == 0:  return -1\n",
    "        tmp = list(x - y for x, y in zip(nums1, nums2))\n",
    "        if any(abs(x) % k != 0 for x in tmp) or sum(tmp): return -1\n",
    "        ret = sum(x // k for x in tmp if x > 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if nums1 == nums2: return 0\n",
    "        if k == 0: \n",
    "            return -1\n",
    "        tmp = list(x - y for x, y in zip(nums1, nums2))\n",
    "        ret = 0\n",
    "        for x in tmp:\n",
    "            if abs(x) % k != 0:\n",
    "                return -1\n",
    "            if x > 0 and x % k == 0:\n",
    "                ret += x // k\n",
    "        return ret if sum(tmp) == 0 and ret else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = (2 * i) + 1\n",
    "            if x > n:\n",
    "                ans += x - n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        k = n//2*2-1 if n % 2 == 0 else n//2*2+1\n",
    "        t = (k - 1) // 2 + 1\n",
    "        return n*t - (1+k)*t//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n%2==0:\n",
    "            return (n//2)**2\n",
    "        return (1+n//2)*(n//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return n * n // 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return n*n//4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += abs((2 * i + 1) - n)\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return n*n//4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return n * n // 2 // 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += abs((2 * i) + 1 - n)\n",
    "        return res // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n % 2 == 1:\n",
    "            n = n // 2\n",
    "            return n * n + n\n",
    "        else:\n",
    "            n = n // 2\n",
    "            return n * n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n % 2 == 1:\n",
    "            return (n // 2) ** 2 + n // 2\n",
    "        return (n // 2) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2==1:\n",
    "            k=(n-1)//2\n",
    "            return k*(k+1)\n",
    "        else:\n",
    "            k=n//2\n",
    "            return k*k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n*n)//4\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n % 2 == 1:\n",
    "            return (n // 2 + 1) * (n // 2)\n",
    "        else:\n",
    "            return (n // 2) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n//2+n%2)*(n//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if not n%2:\n",
    "            return (n // 2) ** 2\n",
    "        else:\n",
    "            return (n // 2) ** 2 + n // 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return n * n // 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n&1:\n",
    "            n = n//2\n",
    "            return (1+n)*n\n",
    "        else:\n",
    "            n = (n-2)//2\n",
    "            return 1+(4+2*n)*n//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n-1+1)*n//2//2 #这个题是几乎自己写的，找到了类似灵茶山的总结思路\n",
    "        #直接对终态进行分析，在一定程度上忽略了中间过程"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        k=n//2\n",
    "        if n%2!=0:\n",
    "            return k*(k+1)\n",
    "        if n%2==0:\n",
    "            return k**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2==0:\n",
    "            return int(n**2/4)\n",
    "        else:\n",
    "            return int((n**2-1)/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n % 2 == 1:\n",
    "            return (n // 2) ** 2 + n // 2\n",
    "        return n ** 2 // 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(n//2):\n",
    "            res += n - 2 * i - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n % 2 == 0:\n",
    "            return int(n * n / 4)\n",
    "        else:\n",
    "            k = n // 2\n",
    "            return int(k * n - k * (n - 1) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n ** 2 - 1) >> 2 if n & 1 else (n >> 1) ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n*n-n%2)//4\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2==1:\n",
    "            return (n*n-1)//4\n",
    "        return n*n//4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2 == 0:\n",
    "            return (n // 2) ** 2\n",
    "        else:\n",
    "            return (n // 2) ** 2 + n // 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n %2==0:\n",
    "            a=0\n",
    "            for i in range(1,n,2):\n",
    "                a+=i\n",
    "            return a\n",
    "        else:\n",
    "            a=0\n",
    "            for i in range(2,n,2):\n",
    "                a+=i\n",
    "            return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2 == 0:\n",
    "            return sum(i for i in range(1, n, 2))\n",
    "        else:\n",
    "            return sum(i for i in range(2, n, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2==0:\n",
    "            return (n*n)//4  #n为偶数：(n^2)/4\n",
    "        else:\n",
    "            return (n*n-1)//4 #n为奇数：(n^2-1)/4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n % 2 != 0:\n",
    "            return ((n-1) + 2)*((n-1)//2)//2\n",
    "        else:\n",
    "            return ((n-1) + 1)*n//2//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        \n",
    "        mid = n\n",
    "        ans = 0\n",
    "        for i in range(n // 2):\n",
    "            cur = 2 * i + 1\n",
    "            ans += mid - cur\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        if n%2==1:\n",
    "            return int((n*n-1)/4)\n",
    "        return int(n*n/4)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n-1+1)*n//2//2 #这个题是几乎自己写的，找到了类似灵茶山的总结思路\n",
    "        #直接对终态进行分析，在一定程度上忽略了中间过程\n",
    "        #复杂度O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n // 2) * (n // 2 + n % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        mid = 2*(n//2)+1\n",
    "        s = sum(abs(2*i+1-mid) for i in range(n))//2\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, n, 2):\n",
    "            res += n - i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        return (n >> 1) * (n & 1) + (n >> 1) * (n >> 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, n: int) -> int:\r\n",
    "\r\n",
    "\r\n",
    "        cnt = 0\r\n",
    "        for i in range(n//2):\r\n",
    "            cur = 2*i + 1\r\n",
    "            cnt += (n - cur)\r\n",
    "        return cnt\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        # num = [(2*i) + 1] for i in range(6)\n",
    "        num = []\n",
    "        for i in range(n):\n",
    "            num.append((2*i) + 1)\n",
    "        ave = sum(num) // n\n",
    "        op_double = 0\n",
    "        for i in num:\n",
    "            tmp = abs(ave - i)\n",
    "            op_double += tmp\n",
    "        return op_double // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, n: int) -> int:\n",
    "        arr=[2*i+1 for i in range(n)]\n",
    "        avg=sum(arr)//n\n",
    "        index=bisect_left(arr,avg)\n",
    "        #print(index)\n",
    "        if avg in arr:\n",
    "            return (1+index)*index\n",
    "        else:\n",
    "            return index*index\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
